并查集

LuoguP3367

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;

int N,M;
int Z,X,Y;
int fa[MAXN];

int find(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}

int main()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;++i) fa[i]=i;
	while(M--)
	{
		scanf("%d%d%d",&Z,&X,&Y);
		if(Z==1)//合并集合 
			fa[find(X)]=fa[find(Y)];
		if(Z==2)//查询是否在一个集合内 
			if(find(X)==find(Y)) printf("Y\n");
			else printf("N\n");
	}
	return 0;
}