本文共 1178 字，大约阅读时间需要 3 分钟。
Floyd联通， 然后为了输出联通分量而新建一个图， 让互相可以打电话的建立一条边， 然后dfs输出联通分量就ok了。
#include #include #include #include #include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 30;int d[MAXN][MAXN], g[MAXN][MAXN], vis[MAXN], n, m;map id;vector word;int get_id(string s){ if(id.count(s)) return id[s]; word.push_back(s); return id[s] = word.size() - 1; //注意这里要减去1}void print(int u, int p){ if(p != 1) printf(", "); cout << word[u]; vis[u] = 1; REP(v, 0, n) if(g[u][v] && !vis[v]) print(v, 0);}int main(){ int kase = 0; while(~scanf("%d%d", &n, &m) && n && m) { if(kase) puts(""); word.clear(); id.clear(); memset(d, 0, sizeof(d)); memset(vis, 0, sizeof(vis)); memset(g, 0, sizeof(g)); while(m--) { string a, b; cin >> a >> b; d[get_id(a)][get_id(b)] = 1; } REP(k, 0, n) REP(i, 0, n) REP(j, 0, n) d[i][j] = d[i][j] || (d[i][k] && d[k][j]); REP(i, 0, n) REP(j, 0, n) g[i][j] = (d[i][j] && d[j][i]); printf("Calling circles for data set %d:\n", ++kase); REP(i, 0, n) if(!vis[i]) { print(i, 1); puts(""); } } return 0; }
转载于:https://www.cnblogs.com/sugewud/p/9819548.html