用到的东西
- 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代码
代码语言：javascript
复制#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<utility>
#include<map>
#include<string>
using namespace std;
const int maxn = 30;
int n, m;
string name1, name2;
int d[maxn][maxn], vis[maxn];
map<string, int> name_set;
vector<string> 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;
}
}
}
}
