这个是用纯并查集写的,求一组hack,90pts
查看原帖
这个是用纯并查集写的,求一组hack,90pts
1215295
discretely楼主2024/3/22 23:21
#include<iostream>
using namespace std;
const int N=205;
int fa[N];
int n;
//问题,同一个人可能有多个父亲,不能当作集合合并 各自在各自的集合里面,设置一个值是作为权值,就是上面没有人的个数
int num[N];
void init(){
	for(int i=1;i<=n;++i) fa[i]=i,num[i]=0;
}
int find(int x){
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
int main(){
	cin>>n;
	init();
	for(int i=1;i<=n;++i){
		int k;
		while(cin>>k){
			num[k]++;
			if(k==0) break;
			//ans[y]++;
			int x=find(i),y=find(k);
			if(x!=y){
				fa[k]=x;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		if(find(i)==i&&!num[i]) ans++;
	//	cout<<find(i)<<endl;
	}
	if(ans>=1) cout<<ans<<endl;
	else cout<<1<<endl;
	return 0;
}
2024/3/22 23:21
加载中...