80pts求调,#4#7
查看原帖
80pts求调,#4#7
592342
WA_automat楼主2022/8/31 11:54

蒟蒻用了unordered_map,但是没过

#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 1010;
int n, m, p, q, parent[N], ans;
bool res[N];
char flag;
unordered_map<int, int> box;
int find(int x) {
	if (parent[x] != x) parent[x] = find(parent[x]);
	return parent[x];
}
void merge(int a, int b) {
	parent[find(a)] = find(b);
}
int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) parent[i] = i;	
	for (int i = 0; i < m; ++i) {
		cin >> flag >> p >> q;
		if (flag == 'F') merge(p, q);
		else {
			box[p] = q;
			box[q] = p;
		}
	}
	for (int i = 1; i <= n; ++i) {
		auto itr = box.find(i);
		if (itr == box.end()) continue;
		int mid = box[i];
		itr = box.find(mid);
		if (itr == box.end()) continue;
		int f = box[mid];
		merge(i, f);
	}
	for (int i = 1; i <= n; ++i) {
		find(i);
		res[parent[i]] = true;
	}
	for (int i = 1; i <= n; ++i) {
		if (res[i]) ++ans;
	}
	cout << ans;
	return 0;
}
2022/8/31 11:54
加载中...