【Calling Circles UVA - 247 】【Floyd + dfs】-白红宇

【Calling Circles UVA - 247 】【Floyd + dfs】

阅读量：4966 次

发布时间：2019-06-12

本文共 1651 字，大约阅读时间需要 5 分钟。

用到的东西

Floyd算法（不考虑路径的长度，只关心两点之间是否有通路，可用于求有向图的传递闭包）

STL map中的count用法

利用dfs输出同一个圈内的名字

题意

题目中给出 n 的人的名字，m组关系，表示前者给后者打电话。如果两个人互相打过电话（直接或者间接），那么这两个人在一个集合。现在要求出所有集合中的人，输出格式看输出实例。

思路

设d[ i ] [ j ] 表示 i 和 j 通话过，如果 d[ i ] [ j ] && d[ j ] [ i ] 那么说明 i 和 j 属于同一个集合。
d[ i ][ j ] = d[ i ][ j ] ||(d[ i ][ k ] && d[ k ][ j ] );

AC代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                using namespace std;const int maxn = 30;int n, m;string name1, name2;int d[maxn][maxn], vis[maxn];map
                
                  name_set;vector
                 
                   namee;void dfs(int cur){ vis[cur] = 1; for(int i = 0; i < n; i++) { if(!vis[i] && d[cur][i] && d[i][cur]) { cout << ", " << namee[i]; dfs(i); } }}int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int cnt = 0; while(scanf("%d%d", &n, &m)) { if(!n && !m) break; ++cnt; if(cnt != 1) cout << endl; name_set.clear(); namee.clear(); memset(d, 0, sizeof(d)); int id = 0; for(int i = 0; i < m; i++) { cin >> name1 >> name2; if(!name_set.count(name1)) name_set[name1] = id++, namee.push_back(name1); if(!name_set.count(name2)) name_set[name2] = id++, namee.push_back(name2); d[name_set[name1]][name_set[name2]] = 1; } for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) d[i][j] = d[i][j] || (d[i][k] && d[k][j]); memset(vis, 0, sizeof(vis)); cout << "Calling circles for data set " << cnt << ":" << endl; for(int i = 0; i < n; i++) { if(!vis[i]) { cout << namee[i]; dfs(i); cout << endl; } } }}