C01【模板】并查集

#include <bits/stdc++.h>
using namespace std;
int fa[210000];//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,x, y,op;i<=m;i++)
	{
		scanf("%d%d%d",&op, &x, &y);
		if(op==1)
		{
			int tx=findfa(x), ty=findfa(y);
			fa[tx]=ty;//这里也可以是fa[ty]=tx;
			//注意：并查集中的合并是两个团体祖先的合并，才能保证团体的所有人都正确的合并。
		}
		else
		{
			if(findfa(x)==findfa(y))printf("Y\n");
			else printf("N\n");
		}
	}
	return 0;
}