UVA-247

题目大意:如果两个人相互打电话(直接或间接),则说他们在同一个电话圈里。

分析:flyod传递闭包

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);

using namespace std;

typedef long long ll;
const int MAXN = 25 + 5;

vector<string> v;//储存所有姓名
int g[MAXN][MAXN];
int n, m;
bool vis[MAXN];

//编号
int num(string& s) {
	for (int i = 0; i < v.size(); i++)
		if (v[i] == s)
			return i;
	v.push_back(s);
	return v.size() - 1;
}

void dfs(int& x) {
	vis[x] = 1;
	for (int i = 0; i < n; i++)
		if (!vis[i] && g[x][i] && g[i][x]) {
			cout << ", " << v[i];
			dfs(i);
		}
}

int main() {
	IOS;
	int xuhao = 0;
	while (1) {
		cin >> n >> m;
		if (!n && !m)
			break;
		else {
			v.clear();
			memset(g, 0, sizeof(g));
			for (int i = 0; i < n; i++)
				g[i][i] = 1;
			while (m--) {
				string s, t;
				cin >> s >> t;
				g[num(s)][num(t)] = 1;
			}
			//flyod求有向图的传递闭包
			for (int k = 0; k < n; k++)
				for (int i = 0; i < n; i++)
					for (int j = 0; j < n; j++)
						g[i][j] |= g[i][k] && g[k][j];
		}
		if (xuhao > 0)
			cout << endl;
		cout << "Calling circles for data set " << ++xuhao << ":" << endl;
		memset(vis, 0, sizeof(vis));
		for (int i = 0; i < v.size(); i++) {
			if (!vis[i]) {
				cout << v[i];
				dfs(i);
				cout << endl; 
			}
		}
	}
	return 0;
}
上一篇:Compound Words UVA - 10391


下一篇:git操作之常见问题解决方案