当前位置: 代码迷 >> 综合 >> UVa - 247 - Calling Circles ( Floyd 传递闭包 )
  详细解决方案

UVa - 247 - Calling Circles ( Floyd 传递闭包 )

热度:96   发布时间:2023-10-09 17:04:12.0

UVa - 247 - Calling Circles ( Floyd 传递闭包 )

UVa - 247 - Calling Circles ( Floyd 传递闭包 )





题目大意:

题目中给出 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 ] );



#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#define N 30 
using namespace std;map<string,int> v; //存储名字对应编号 
vector<string> name;//存储名字 用来遍历输出 
string s1,s2;
int n,m,cnt=0;
int d[N][N];	//建立邻接矩阵 
int vis[N]; //访问标记 void Floyd(){for(int k=0 ;k<n ;k++){for(int i=0 ;i<n ;i++){for(int j=0 ;j<n ;j++){//d[i][j]表示i是否给j直接或间接打过电话 d[i][j] = d[i][j]||(d[i][k]&&d[k][j]);}}}
}
//dfs遍历输出 
void dfs(int u){vis[u] = 1;for(int i=0 ;i<n ;i++){if(!vis[i]&&d[u][i]&&d[i][u]){cout<<", "<<name[i];dfs(i);}}
}//数据输入处理 
void init(){name.clear();v.clear();memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));int id = 0;for(int i=0 ;i<m ;i++){cin>>s1>>s2;if(!v.count(s1)) {v[s1] = id++;name.push_back(s1);}if(!v.count(s2)){v[s2] = id++;name.push_back(s2);} d[v[s1]][v[s2]] = 1;}
}int main(){while(scanf("%d%d",&n,&m)!=EOF&&n&&m){cnt++;//数据输入 init();//数据处理 Floyd();if(cnt>1){printf("\n");}printf("Calling circles for data set %d:\n",cnt);//输出 for(int i=0 ;i<n ;i++){if(!vis[i]){cout<<name[i];dfs(i);printf("\n");}}}return 0;
} 




  相关解决方案