vijos p1876 bfs+map

题意：

Xiaodao是一位喜欢参加ACM比赛的孩子.

所谓ACM比赛, 是一种团队比赛.

每一次比赛, 每队需要由恰好三位选手组成.

现在, Xiaodao希望组建一支新的队伍, 在这之前, 他需要知道每一位朋友有多少可能成为自己的好队友.

他计划给每一位朋友做出一个等级标号.

Xiaodao本人的等级标号为0.

如果一位朋友曾经和Xiaodao组队参加过比赛, 那么就标号为1.

如果一位朋友并没有与Xiaodao组队参加过比赛, 但是曾经与一位"与Xiaodao一起参加过比赛的人"组队参加过比赛. 那么就标号为2.

如果一位朋友无法标号为小于等于 k 的整数, 但是曾经与"标号为k的人"一起参加过比赛, 那么便可以标号为k+1.

其余的朋友们, 便无法给出编号, 我们记为"undefined".

现在, 我们给出了 n 组曾经参赛过的队伍, 每一组中给出了三位选手的名字.

我们希望知道每一位涉及到的选手应该被给予什么样的标号.

链接：点我

邻接表和邻接矩阵都没满分

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt,u,tot;

 int c[MAXN][MAXN],dist[MAXN],vis[MAXN];

 string a[MAXN];

 struct Node

 {

     int to,next;

 }edge[MAXN*];

 int head[MAXN];

 int tol;

 void init()

 {

     tol=;

     memset(head,-,sizeof(head));

 }

 void addedge(int a,int b)

 {

     edge[tol].to=b;

     edge[tol].next=head[a];

     head[a]=tol++;

     edge[tol].to=a;

     edge[tol].next=head[b];

     head[b]=tol++;

 }

 void bfs()

 {

     queue<int> q;

     cl(vis);

     vis[u]=;

     dist[u]=;

     int now,next;

     q.push(u);

     while(!q.empty())

     {

         now=q.front();

         q.pop();

         for(int i=head[now];i!=-;i=edge[i].next)

         {

             next=edge[i].to;

             if(!vis[next])

             {

                 dist[next]=dist[now]+;

                 vis[next]=;

                 q.push(next);

             }

         }

     }

 }

 map<string,int> mp;

 string s="Xiaodao";

 int main()

 {

     int i,j,k;

     /*#ifndef ONLINE_JUDGE

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

     #endif*/

     scanf("%d",&n);

     tot=;

     cl(c);

     string s1,s2,s3;

     bool flag=;

     init();

     int i1,i2,i3;

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

     {

         cin>>s1,cin>>s2,cin>>s3;

         if((s1==s||s2==s||s3==s)&&!flag)   u=tot,flag=;

         i1=mp[s1],i2=mp[s2],i3=mp[s3];

         if(!mp[s1])    a[tot]+=s1,i1=mp[s1]=tot++;

         if(!mp[s2])    a[tot]+=s2,i2=mp[s2]=tot++;

         if(!mp[s3])    a[tot]+=s3,i3=mp[s3]=tot++;

         addedge(i1,i2),addedge(i1,i3),addedge(i2,i3);

     }

     bfs();

     sort(a+,a+tot+);

     for(i=;i<=tot;i++)

     {

         int l=a[i].length();

         if(l==)    continue;

         for(j=;j<l;j++)printf("%c",a[i][j]);

         int id=mp[a[i]];

         if(!vis[id])    printf(" undefined\n");

         else printf(" %d\n",dist[id]);

     }

 }