hdu 4039 The Social Network

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4039

题目分类：字符串+bfs

题意：给一个人际关系图，根据关系图，给一个人推荐一个人认识

题目分析：

根据样例画出的关系图

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

map<string,int>mp;

vector<int>G[N*];

vector<string> ans;

char s1[];

char s2[];

char ss[];

char s[N*][];

int Stack[N*];

int vis[N*];

bool bfs(int u)

{

    memset(vis,,sizeof(vis));

    vis[u]=-;

    queue<int>q;

    for(int i=;i<G[u].size();i++)

    {

        q.push(G[u][i]);

        vis[G[u][i]]=-;

    }

    int siz=-;

    int company=;

    while(!q.empty())

    {

        u=q.front();

        q.pop();

        for(int i=;i<G[u].size();i++)

        {

            int v=G[u][i];

            if(vis[v]==-) continue;

            vis[v]++;

            if(siz<vis[v])

            {

                siz=vis[v];

                company=;

                Stack[]=v;

            }

            else if(siz==vis[v])

            {

                Stack[company++]=v;

            }

        }

    }

    if(siz<) return false;

    ans.clear();

    for(int i=;i<company;i++)

        ans.push_back(s[Stack[i]]);

    sort(ans.begin(),ans.end());

    for(int i=;i<ans.size();i++)

    {

        cout<<ans[i];

        if(i<ans.size()-)

            printf(" ");

    }

    printf("\n");

    return true;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

    #endif

    int t,n,m;

    scanf("%d",&t);

    for(int kase=;kase<=t;kase++)

    {

        mp.clear();

        scanf("%d %d",&n,&m);

        for(int i=;i<=*n;i++)

            G[i].clear();

        int top=;

        int num1,num2;

        while(n--)

        {

            scanf("%s %s",s1,s2);

            if(mp.find(s1)==mp.end())

            {

                mp[s1]=++top;

                memcpy(s[top],s1,sizeof s1);

                num1=top;

            }

            else

                num1=mp.find(s1)->second;

            if(mp.find(s2)==mp.end())

            {

                mp[s2]=++top;

                memcpy(s[top],s2,sizeof s2);

                num2=top;

            }

            else

                num2=mp.find(s2)->second;

            G[num1].push_back(num2);

            G[num2].push_back(num1);

        }

        printf("Case %d:\n",kase);

        while(m--)

        {

            scanf("%s",ss);

            int i=mp.find(ss)->second;

            if(bfs(i)==false)

                puts("-");

        }

    }

    return ;

}