并查集

luogu3367

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 200005
using namespace std; 

int n,m,fa[N]; 

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

void Merge(int x,int y)
{
	x=findf(x);y=findf(y);
	fa[x]=y;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) Merge(x,y);
		else
		{
			if(findf(x)==findf(y)) printf("Y
");
			else printf("N
");
		} 
	}
	return 0;
}