首页 > 其他分享 >Calling Circles UVA - 247

Calling Circles UVA - 247

时间:2022-08-15 10:03:13浏览次数:82  
标签:Circles cnt get int vis 247 mp UVA include

原题链接

思路

把最短路换成是否可达即可

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 30;
int test_case = 1;
int n,m;
unordered_map <string,int> mp;
unordered_map <int,string> name;
int cnt = 0;
bool g[N][N];
bool vis[N];
vector <int> ans;
int get (string s) {
	if (!mp.count (s)) {
		mp[s] = ++cnt;
		name[cnt] = s;
	}
	return mp[s];
}
int main () {
	while (cin >> n >> m,n && m) {
		mp.clear (),name.clear ();
		memset (g,false,sizeof (g));
		memset (vis,false,sizeof (vis));
		cnt = 0;
		while (m--) {
			string a,b;
			cin >> a >> b;
			g[get (a)][get (b)] = true;
		}
		for (int k = 1;k <= n;k++) {
			for (int i = 1;i <= n;i++) {
				for (int j = 1;j <= n;j++) g[i][j] |= g[i][k] & g[k][j];
			}
		}
		cout << "Calling circles for data set " << test_case++ << ":" << endl;
		for (int i = 1;i <= n;i++) {
			if (vis[i]) continue;
			ans.clear ();
			ans.push_back (i);
			for (int j = 1;j <= n;j++) {
				if (i != j && !vis[j] && g[i][j] && g[j][i]) {
					ans.push_back (j);
					vis[j] = true;
				}
			}
			for (int i = 0;i < ans.size ();i++) {
				if (i) cout << ", ";
				cout << name[ans[i]];
			}
			cout << endl;
		}
	}
    return 0;
}

标签:Circles,cnt,get,int,vis,247,mp,UVA,include
From: https://www.cnblogs.com/incra/p/16587203.html

相关文章

  • UVA10089 Repackaging
    设第\(i\)种包装中\(j\)尺寸的杯子数量为\(S_{ij}\),第\(i\)种包装选取的数量为\(a_i\),若能够按照要求进行重新打包,有\[\begin{cases}a_1S_{11}+a_2S_{21}......