【并查集模板】并查集模板 luogu-3367

题目描述

简单的并查集模板

输入描述

第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N。

分析

简单的模板，解释留到算法微解读

AC代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
int fa[10000+5];
inline int read(){
	int X=0,w=0; char ch;
	while (!isdigit(ch)) {w|=ch=='0'; ch=getchar();}
	while (isdigit(ch)) {X=(X<<3)+(X<<1)+(ch^48);ch=getchar();}
	return w?-X:X;
}
int gf(int x) {
	if (fa[x]==x) return fa[x];
	else return fa[x]=gf(fa[x]);
}
int main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++) fa[i]=i;
	while (m--) {
		int x=read(),y=read(),z=read(),p1=gf(y),p2=gf(z);
		if (x==2) {
			if (p1==p2) printf("Y
");
			else printf("N
");
		}
		else if (p1!=p2) fa[p1]=p2;
	}
	return 0;
}