(Floyd+dfs)Calling Circles，UVA24

传送门https://vjudge.net/problem/UVA-247
题意：如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f，而f不打给e，则不能推出e和f在同一个电话圈。输入n(n<=25)个人的m次电话，找出所有的电话圈。人名只包含字母，不超过25个字符，且不重复。

分析：本题一看就是求有向图的强连通分量问题。可以用tarjan解决。但是注意到数据比较小，还可以想到另外一个算法——floyd。在有向图中，有时不必关心路径的长度，只关心每两点之间是否有通路，则可以用1和0表示“连通”和“不连通”。这样，就可以用floyd解决了：dp[i][j]=dp[i][j]||(dp[i][k]&&dp[k][j])。这样的结果称为有向图的传递闭包(Transitive Closure)。

利用map的特性进行编号，然后利用floyd求出传递闭包，最后又用到DFS进行连通块的输出

#include<stdio.h>  
#include<map>  
#include<string>  
#include<iostream>  
#include<string.h>  
#include<vector>  
using namespace std;  
   int n,m,cas=1;  
map<string,int>name;  //用来为string编号 
int f[30][30];  //用来储存并修改连通信息 
int vis[30];  //标记数组，防止重复输出组合 
vector<string>Name;  // 
void dfs(int u)  //dfs搜索连通块 
{  
    vis[u]=1;  
    for(int i=0;i<n;i++)  
    if(f[u][i]&&f[i][u]){  
        if(!vis[i]){  
            cout<<", "<<Name[i];  
            dfs(i);  
        }  
    }  
}  
  
int main()  
{  
  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        name.clear();  //初始化map 
        Name.clear();  //初始化vector 
        memset(f,0,sizeof f);  //初始化连通数组 
        memset(vis,0,sizeof vis);  //初始化标记数组 
       // if(cas>1) puts("");  
        int id=0;  //索引 
        if(n==0&&m==0) break;//输入0 0判定退出  
        for(int i=0;i<m;i++){  //输入m条连通信息 
            string a,b;  
            cin>>a>>b;  
            if(!name.count(a))  //如果么有分配索引，那么分配 
            {  
                name[a]=id++;  
                Name.push_back(a);  
            }  
            if(!name.count(b))  
            {  
                name[b]=id++;  
                Name.push_back(b);  
            }  
            int x=name[a],y=name[b];  
            f[x][y]=1;  //连通 
        }  
        for(int k=0;k<n;k++)  //Floyd 
            for(int i=0;i<n;i++)  
                for(int j=0;j<n;j++)  
                f[i][j]=(f[i][j]||(f[i][k]&&f[k][j]));  //传递闭包 
        if(cas>1)  
            cout<<endl;  
        cout<<"Calling circles for data set " << cas++ <<":" << endl;  
        for(int i=0;i<n;i++){  //寻找连通块（标记是关键） 
            if(!vis[i]){  
             cout<<Name[i];  
             dfs(i);  
             cout<<endl;  
            }  
        }  
    }  
    return 0;  
}