C01【模板】并查集

#include <bits/stdc++.h>
using namespace std;
int fa[110000];//fa[x]表示x的上级节点
/*
重点：以下是findfa()函数的正常版本，但会超时。一定要理解为什么超时？
return findfa(fa[x]) 和 return fa[x]=findfa(fa[x]) 都是返回fa[x]的值，但不同点在于：
后者“偷偷”修改了上级节点的值，相当于压缩了求祖先节点的路径（著名的并查集路径压缩技巧）
int findfa(int x)//找x所在团体的代表节点（祖先节点）
{
	if(fa[x]==x)return fa[x];
	else        return findfa(fa[x]);
}
*/

int findfa(int x)//找x所在团体的代表节点（祖先节点）
{若fa[x]==x则返回fa[x]，否则递归查找并压缩路径
	if(fa[x]==x)return fa[x];
	else        return fa[x]=findfa(fa[x]);
}
int main()
{
	int n, m;scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x, y;scanf("%d%d", &x, &y);
		int tx=findfa(x), ty=findfa(y);
		fa[tx]=ty;//这里也可以是fa[ty]=tx;
        //注意：并查集中的合并是两个团体祖先的合并，才能保证团体的所有人都正确的合并。
	}
	int ans=0;
	for(int i=1;i<=n;i++)if(fa[i]==i)ans++;
	printf("%d\n", ans);
	return 0;
}

C01【模板】并查集

#include<bits/stdc++.h>
using namespace std;
int fa[110000];//fa[x]表示x的上级节点
/*
重点：以下是findfa()函数的正常版本，但会超时。一定要理解为什么超时？
return findfa(fa[x]) 和 return fa[x]=findfa(fa[x]) 都是返回fa[x]的值，但不同点在于：
后者“偷偷”修改了上级节点的值，相当于压缩了求祖先节点的路径（著名的并查集路径压缩技巧）
int findfa(int x)//找x所在团体的代表节点（祖先节点）
{
	if(fa[x]==x)return fa[x];
	else        return findfa(fa[x]);
}
*/

int findfa(int x)//找x所在团体的代表节点（祖先节点）
{
	if(fa[x]==x)return fa[x];
	else        return fa[x]=findfa(fa[x]);
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		int tx=findfa(x),ty=findfa(y);
		fa[tx]=ty;//这里也可以是fa[ty]=tx;
        //注意：并查集中的合并是两个团体祖先的合并，才能保证团体的所有人都正确的合并。
	}
	int ans=0;
	for(int i=1;i<=n;i++)if(fa[i]==i)ans++;
	printf("%d\n",ans);
	return 0;
}