前言

父父子子，君君臣臣。。。并查集也。。。

1.思想

用一个fa[]数组储存该元素的父亲，如果两个元素的父亲是同一个元素，那么它们就在同一个并查集里。

2.并查集模板题

【题目链接】
洛谷【3367】
【题目描述】
如题，现在有一个并查集，你需要完成合并和查询操作。
【输入格式】
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi；
当Zi=1时，将Xi与Yi所在的集合合并；
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N。
【输出格式】
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N。
【输入样例】

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

【输出样例】

N
Y
N
Y

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<iostream>
#define M 500500
using namespace std;
int n,m;
int fa[M];
inline void reinit()
{
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
	}
}
int find(int x)
{
	if(x!=fa[x])
		fa[x]=find(fa[x]);
	return fa[x];
}
int pd(int x,int y)
{
	if(find(x)==find(y)) return 1;
	return 0;
}
inline void un(int x,int y)
{
	fa[find(x)]=find(y);
}
int main()
{
	scanf("%d%d",&n,&m);
	reinit();
	int t,ta,tb;
	while(m--)
	{
		scanf("%d%d%d",&t,&ta,&tb);
		if(t==1)
		{
			un(ta,tb);
		}
		if(t==2)
		{
			if(pd(ta,tb))
				printf("Y\n");
			else
				printf("N\n");
		}
	}
	return 0;
}