Super Phyllis（穷举+搜索）

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2723

题意：给出一些字符串u，v,代表u->v,问有几条边是多余的，也就是说去掉那些边后，u仍能到达v。

思路：穷举每条边，试着去掉该边，bfs搜索两个点是否仍然可达。

 #include<stdio.h>

 #include<iostream>

 #include<string.h>

 #include<map>

 #include<queue>

 #include<vector>

 #include<string>

 #include<algorithm>

 using namespace std;

 char s1[],s2[],s[][];

 map<string,int>f;

 vector<int>graph[];

 int Map[][],vis[];

 int n;

 int cnt;

 struct node

 {

     char s1[];

     char s2[];

 }edge[],tmp[];

 int cmp(const node a, const node b)

 {

     if(strcmp(a.s1,b.s1) == )

         return strcmp(a.s2,b.s2)<;

     return strcmp(a.s1,b.s1)<;

 }

 bool bfs(int s, int t)

 {

     queue<int> que;

     while(!que.empty())

         que.pop();

     vis[s] = ;

     que.push(s);

     while(!que.empty())

     {

         int u = que.front();

         que.pop();

         if(u == t)

             return true;

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

         {

             int v = graph[u][i];

             if(!vis[v] && Map[u][v])

             {

                 que.push(v);

                 vis[v] = ;

             }

         }

     }

     return false;

 }

 int main()

 {

     int item = ;

     while(cin >> n)

     {

         if(n == ) break;

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

             graph[i].clear();

         f.clear();

         memset(Map,,sizeof(Map));

         cnt = ;

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

         {

             cin>>s1>>s2;

             if(!f[s1])

             {

                 f[s1] = ++cnt;

                 strcpy(s[cnt],s1);

             }

             if(!f[s2])

             {

                 f[s2] = ++cnt;

                 strcpy(s[cnt],s2);

             }

             graph[ f[s1] ].push_back( f[s2] );

             Map[ f[s1] ][ f[s2] ] = ;

         }

         int res = ;

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

         {

             for(int j = ; j < (int)graph[i].size(); j++)

             {

                 int v = graph[i][j];

                 memset(vis,,sizeof(vis));

                 Map[i][v] = ;

                 if(bfs(i,v))

                 {

                     strcpy(edge[res].s1,s[i]);

                     strcpy(edge[res].s2,s[v]);

                     res++;

                 }

                 else Map[i][v] = ;

             }

         }

         sort(edge,edge+res,cmp);

         printf("Case %d: ",item++);

         int t = ;

         if(res)

             tmp[t++] = edge[];

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

         {

             if(strcmp(edge[i].s1,edge[i-].s1) ==  && strcmp(edge[i].s2,edge[i-].s2) == )

                 continue;

             else

             {

                 tmp[t++] = edge[i];

             }

         }

         printf("%d",t);

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

         {

             printf(" %s,%s",tmp[i].s1,tmp[i].s2);

         }

         printf("\n");

     }

     return ;

 }