《类似并查集但又不是并查集的东西怎么搞》
查看原帖
《类似并查集但又不是并查集的东西怎么搞》
1013950
__youzimo2014__楼主2024/12/6 17:00

faxfa_x 表示 xx 可以 faxfa_x 拷贝。

更多细节见代码:

代码注释会有一些关于树的习惯叫法,请勿带入题目。

// byLuoguUID : 1013950
// submitPID  : P2835

#include <bits/stdc++.h>
using namespace std;
int fa[205], n;
void init() {
	for (int x = 1; x <= n; x++) {
		fa[x] = x;
	}
}
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
	fa[x] = y; // 因为x的祖先不一定能从y的祖先拷贝数据,但是x一定能从y拷贝数据。
	// 把 fa[x] 改成 y,一定是不劣的,因为不管怎么样他都可以拷贝别人的数据,从谁那里拷贝就不重要了。 
}
int main() {
	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		while (true) {
			int tmp;
			cin >> tmp;
			if (tmp == 0) break;
			if (find(tmp) != find(i)) merge(tmp, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		find(i); // 压缩路径,把每个人的父亲都变成祖先 
	}
	sort(fa+1, fa+n+1);
	int ans = 0, now_fa = 0;
	for (int i = 1; i <= n; i++) {
		if (fa[i] != now_fa) {
			now_fa = fa[i];
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}
2024/12/6 17:00
加载中...