UVA 247"Calling Circles"（floyd求传递闭包+SCC）

传送门

题意：

　　如果两个人相互打电话（直接或间接），则说他们在同一个电话圈里。

　　(a,b) 表示 a 打给 b；

　　例如，(a,b),(b,c),(c,d),(d,a)，则这四个人在同一个电话圈里；

　　输入 n(n≤25) 个人的 m 次电话，找出所有的电话圈，输出每个电话圈里的人名（无序）。

题解：

　　首先用floyd求出传递闭包，构造新图；

　　然后在新图上跑一遍SCC求解；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define memF(a,b,n) for(int i=0;i <= n;a[i]=b,++i);

 const int maxn=;

 int n,m;

 int num;

 int head[maxn];

 struct Edge

 {

     int to;

     int next;

 }G[maxn*maxn*];

 void addEdge(int u,int v)

 {

     G[num]={v,head[u]};

     head[u]=num++;

 }

 map<string ,int >f;

 map<int ,string >g;

 bitset<maxn>_bit[maxn];

 int col[maxn];

 struct SCC

 {

     vector<int >vs;

     bool vis[maxn];

     void DFS(int u)

     {

         vis[u]=true;

         for(int i=head[u];~i;i=G[i].next)

         {

             int v=G[i].to;

             if(vis[v] || (i&))

                 continue;

             DFS(v);

         }

         vs.push_back(u);

     }

     void RDFS(int u,int k)

     {

         vis[u]=true;

         col[u]=k;

         for(int i=head[u];~i;i=G[i].next)

         {

             int v=G[i].to;

             if(vis[v] || !(i&))

                 continue;

             RDFS(v,k);

         }

     }

     void scc()

     {

         vs.clear();

         memF(vis,false,n);

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

             if(!vis[i])

                 DFS(i);

         memF(vis,false,n);

         int k=;

         for(int i=vs.size()-;i >= ;--i)

             if(!vis[vs[i]])

                 RDFS(vs[i],++k);

     }

 }_scc;

 vector<int >vs[maxn];

 void Solve()

 {

     for(int i=;i <= n;++i)///传递闭包

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

             if(_bit[j][i])

                 _bit[j] |= _bit[i];

     for(int i=;i <= n;++i)///构图

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

             if(_bit[i][j])

             {

                 addEdge(i,j);

                 addEdge(j,i);

             }

     _scc.scc();

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

         vs[i].clear();

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

         vs[col[i]].push_back(i);

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

     {

         bool flag=false;

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

         {

             if(!flag)

             {

                 cout<<g[vs[i][j]];

                 flag=true;

             }

             else

                 cout<<", "<<g[vs[i][j]];

         }

         if(flag)

             printf("\n");

     }

 }

 void Init()

 {

     num=;

     memF(head,-,n);

     f.clear();

     g.clear();

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

         _bit[i].reset();

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

     bool flag=false;

     int kase=;

     while(~scanf("%d%d",&n,&m) && n+m)

     {

         Init();

         int k=;

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

         {

             string s1,s2;

             cin>>s1>>s2;

             if(!f.count(s1))

             {

                 f[s1]=++k;

                 g[k]=s1;

             }

             if(!f.count(s2))

             {

                 f[s2]=++k;

                 g[k]=s2;

             }

             _bit[f[s1]].set(f[s2]);

         }

         if(flag)

             printf("\n");

         flag=true;

         printf("Calling circles for data set %d:\n",++kase);

         Solve();

     }

     return ;

 }