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
58
59
60
61
62
|
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAXN 20001
int fa[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x)
{
if (x == fa[x])
return x;
else {
fa[x] = find(fa[x]);//父节点设为根节点
return fa[x];//返回父节点
}
}
void unionn(int i, int j) {
int i_fa = find(i);//找到i的祖先
int j_fa = find(j);//找到j的祖先
fa[i_fa] = j_fa;//i的祖先指向j的祖先。其实j的祖先指向i的祖先也是可以的}
}
int main() {
/*
输入:
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
*/
int n, m, x, y, q;
scanf("%d", &n);
init(n);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
unionn(x, y);
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &x, &y);
if (find(x) == find(y))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
|
