亲戚问题

【问题描述】若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。(人数≤5000,亲戚关系≤5000,询问亲戚关系次数≤5000)。

数据输入:
第一行:三个整数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是否具有亲戚关系。

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

int father[100];
int getfather(int a){
if (father[a] == a) {
return father[a];
}
else return getfather(father[a]);
}
void join(int x,int y){
int fx = getfather(x);
int fy = getfather(y);
if (fx == fy) {
return ;
}
if (fx != fy) {
father[fx] = fy;
}
}


int main(int argc, const char * argv[]) {
int n,m,p;
cin >> n >> m >> p;
for (int i = 1; i <= n; i++) {
father[i] = i;
}
int a,b;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
join(a, b);
}
for (int i = 0; i < p; i++) {
cin >> a >> b;
if (getfather(a) == getfather(b)) {
cout << "Yes" << endl;
}
else cout << "No" << endl;
}

return 0;
}
script>