一个可能是非正解的并查集,求验证思路正确性
查看原帖
一个可能是非正解的并查集,求验证思路正确性
231543
bloodstalk楼主2022/5/10 10:14

我的思路就是让i的祖先与x合并,而不是与x的祖先和合并,然后就wa了 #9 #11 ,请问我有什么遗漏的点

#include<bits/stdc++.h>
using namespace std;

int a[201];
int fa[201],group[201],cnt;
int n;

int find(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		int x;
		while(scanf("%d",&x) && x)
		{
			int x1=find(i);
			if(x1 != x) fa[x]=x1;/*i的祖先和x合并*/
		}
	}
	for(int i=1;i<=n;i++)
		if(!group[find(i)]) /*看看祖先节点有多少个*/{cnt++;group[find(i)]=1;}
	printf("%d",cnt);
	return 0;
}
2022/5/10 10:14
加载中...