题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,MN,M ,表示共有 NN 个元素和 MM 个操作。

接下来 MM 行，每行包含三个整数 Z_i,X_i,Y_iZi​,Xi​,Yi​ 。

当 Z_i=1Zi​=1 时，将 X_iXi​ 与 Y_iYi​ 所在的集合合并。

当 Z_i=2Zi​=2 时，输出 X_iXi​ 与 Y_iYi​ 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Z_i=2Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例

输入 #1复制

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1复制

N
Y
N
Y

说明/提示

对于 30\%30% 的数据，N \le 10N≤10，M \le 20M≤20。

对于 70\%70% 的数据，N \le 100N≤100，M \le 10^3M≤103。

对于 100\%100% 的数据，1\le N \le 10^41≤N≤104，1\le M \le 2\times 10^51≤M≤2×105，1 \le X_i, Y_i \le N1≤Xi​,Yi​≤N，Z_i \in \{ 1, 2 \}Zi​∈{1,2}。

1.这是一个简单的并查集问题。

2.当Z的值是1的时候我们需要去寻找X，Y的祖宗，如果不属于同一个集合，我们就需要一个靠左原则（你也可以使用靠右原则），把右边找到的“头”（也就是祖宗）改成在X集合中找到的头，就可以了。

3.当Z的值是2时，我们只需要分别找到，X，Y的祖先，然后判断是否相等即可，如果相等输出Y，否则输出N。

4.当然初始化是很重要的。

代码如下：

#include<stdio.h>
#define N 10010
int a[N];
int getf(int x)
{if(x==a[x]) return x;else{int p;p=getf(a[x]);a[x]=p;return p;}
}
int pd(int x,int y)
{int p,q;p=getf(x);q=getf(y);if(p==q) printf("Y\n");else printf("N\n");return 0;
}
int merge(int x,int y)
{int p,q;p=getf(x);q=getf(y);if(p!=q){a[q]=p;}
}
int main()
{int n,m,i,j,x,y,z;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)a[i]=i;for(i=0;i<m;i++){scanf("%d%d%d",&z,&x,&y);if(z==2) pd(x,y);else merge(x,y);}return 0;
}