#9,#11 WA 并查集为什么不行??
查看原帖
#9,#11 WA 并查集为什么不行??
194952
SUPERMAN0109楼主2022/10/3 15:25
#include <iostream>
#include <iomanip> 

using namespace std;

int fa[201];

int findn(int x) {
	if(fa[x]!=x)
		fa[x]=findn(fa[x]);
	return fa[x];
}

void link(int m,int n) {
	fa[m]=n;
}

int main() {
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	int k,r1,r2;
	for(int i=1;i<=n;i++) {
		cin >> k;
		while(k!=0) {
			r1=findn(i);
			r2=findn(k);
			if(r1!=r2&&fa[r2]!=r1&&fa[r1]!=fa[r2])
				link(k,i);
			cin >> k;
		}
	}
	int num=0;
	for(int i=1;i<=n;i++) {
		if(fa[i]==i)
			num++;
	}
	cout << num << endl;
	return 0;
}
2022/10/3 15:25
加载中...