求助90pts悬赏一关
查看原帖
求助90pts悬赏一关
742533
hzxphy楼主2023/7/25 10:35
#include <bits/stdc++.h>
using namespace std;

int prt[10010];
void InitSet(int N) {
	for (int i = 1; i <= N; i++) {
		prt[i] = i;
	}
}
int GetFather(int U) {
	if (prt[U] == U) return U;
	prt[U] = GetFather(prt[U]);
	return prt[U];
}
void Union(int U, int V) {
	int x = GetFather(U);
	int y = GetFather(V);
	if (x != y) prt[x] = y;
}
bool Same(int U, int V) {
	return GetFather(U) == GetFather(V);
}
bool v[1010][1010];
set<int> st;
int main() {
	int N, M;
	cin >> N >> M;
	InitSet(N);
	for (int i = 1; i <= M; i++) {
		char opt;
		int p, q;
		cin >> opt >> p >> q;
		if (opt == 'F') {
			Union(p, q);
		}
		else {
			if (!v[p][q]) {
				v[p][q] = true;
			}
			for (int j = 1; j <= N; j++) {
				if (j == q) continue;
				if (v[p][j]) {
					Union(j, q);
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		st.insert(GetFather(i));
	}
	cout << st.size() << '\n';
	return 0;
}

#7 输出了25 link

2023/7/25 10:35
加载中...