UVa247 Calling Circles(Floyd warshall算法)

题意

给定两个人相互打电话，如果a打给b,b打给c,c打给a，则说a,b,c在同一电话圈中。给出n个人的m次通话，输出所有的电话圈

思路

用graph[u][v]=1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]=1表示u,v之间有直接或者间接打电话。如果graph[u][v] = 1并且graph[v][u]=1，说明u和v是在同一个电话圈

代码如下

#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;
}