并查集模板

四月 14, 2018 1396

并查集模板

题目链接

题目描述

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

输入输出格式

输入格式：

第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：

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

输入输出样例

输入输出样例1

input:

1
2
3
4
5
6
7
8
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

output:

1
2
3
4
5
N
Y
N
Y

数据说明

时空限制：1000ms,128M

数据规模：

对于30%的数据，N<=10，M<=20；

对于70%的数据，N<=100，M<=1000；

对于100%的数据，N<=10000，M<=200000。

代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 10000 + 10;

int U[MAXN], m, n;

inline int Find(int x) {
	if (U[x] < 0) return x;
	return U[x] = Find(U[x]);
}

inline void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (x == y) return;
	U[x] += U[y];
	U[y] = x; 
}

int main() {
	ios::sync_with_stdio(false);
	scanf("%d %d", &n, &m);
	for (int i = 1;i < MAXN;i++) U[i] = -1;
	int z;
	for (int i = 0;i < m;i++) {
		scanf("%d", &z);
		int x, y;
		switch(z) {
			case 1:{
				scanf("%d %d", &x, &y);
				Union(x, y);
				break;
			}
			case 2:{
				scanf("%d %d", &x, &y);
				if (Find(x) == Find(y)) puts("Y");
				else puts("N");
				break;
			}
		}
	}
	return 0;
}