題意

給定兩個(gè)人相互打電話，如果a打給b,b打給c,c打給a，則說a,b,c在同一電話圈中。給出n個(gè)人的m次通話，輸出所有的電話圈

思路

用graph[u][v]=1表示u和v之間有打電話。在使用floyd算法計(jì)算所有的點(diǎn)對(duì)之間的值。graph[u][v]=1表示u,v之間有直接或者間接打電話。如果graph[u][v] = 1并且graph[v][u]=1，說明u和v是在同一個(gè)電話圈

代碼如下

#include <bits/stdc++.h>using namespace std;const int N = 30;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)int n, m;
int graph[N][N];
bool vis[N];
map<string, int> nameMap;
vector<string> names;int getId(const string& name)
{if (!nameMap.count(name)){int size = names.size();nameMap[name] = size;names.push_back(name);}return nameMap[name];
}void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint kase = 1;while (cin >> n >> m) {if (n == 0 && m == 0) {break;}if (kase > 1) {cout << endl;}nameMap.clear();names.clear();memset(graph, 0, sizeof(graph));fill(vis, vis + N, false);_for(i, 0, m) {string a, b;cin >> a >> b;int u = getId(a);int v = getId(b);graph[u][v] = 1;}_for(k, 0, n) {_for(i, 0, n) {_for(j, 0, n) {graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);}}}cout << "Calling circles for data set " << kase << ":" << endl;_for(u, 0, n) {if (vis[u]) {continue;}vis[u] = true;cout << names[u];_for(v, 0, n) {if (!vis[v] && graph[u][v] && graph[v][u]) {vis[v] = true;cout << ", " << names[v];}}cout << endl;}kase++;}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}