「codevs1073」并查集

发表于 | 分类于

题目链接

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入描述 Input Description

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

输出描述 Output Description

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

样例输入 Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

样例输出 Sample Output

1
2
3
4
5
Yes
Yes
No

并查集裸题，就当给dalao递板子了，虽然我比较弱，还是说一下自己的理解；其实并查集呢，我们就把它想象成一棵树，存在只有自己一个节点的树，也存在拥有多个节点的树，只要是连通，我们就说他们位于同一个树中，合并并查集呢，就是将两棵树的树根连接在一起咯；

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
#include <cstdio>
using namespace std;
inline int read() {
	char ch = getchar(); int res = 0; int flag = 1;
	while(ch < '0' || ch > '9') {if(ch == '-') flag = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {res = res * 10 + ch - '0'; ch = getchar();}
	return (res * flag);
}
//高天宇的快读，大家可以拿去用；
int n, m, p;
int father[5000 + 5];
inline int find(int x) {
	return father[x] == x ? x : father[x] = find(father[x]);
}
//寻找父亲（根节点）的操作；
//路径压缩，回溯的时候就顺带把父亲们直接连接在根节点上，那么节点们寻找根节点的路径
//就变短了，所以称为路径压缩；
inline void merge(int x, int y) {
	int r1 = find(x); int r2 = find(y);
	if(r1 == r2) return;
	else father[r1] = r2;
}
//合并操作；如果不是同一个父亲（根节点），则把两棵子树通过各自的根节点连在一起；
inline bool judge(int x, int y) {
	return find(x) == find(y) ? true : false;
}
//判断是不是同一个父亲；
int main() {
	n = read(); m = read(); p = read();
	for(int i = 1; i <= n; ++ i) father[i] = i;
    //千万别忘了初始化！！！
	for(int i = 1; i <= m; ++ i) {
		int x = read(); int y = read();
		merge(x, y);
	}
	for(int i = 1; i <= p; ++ i) {
		int x1 = read(); int x2 = read();
		if(judge(x1, x2)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}