找亲戚——并查集小题

原创

题目大意为给出n个人，编号为1-n，给出m对亲戚关系，然后指定两个人，问他们是否为亲戚。

若a和b是亲戚，b和c是亲戚，则a和c是亲戚；若a和b是亲戚，则a的亲戚和b的亲戚都互成为亲戚。

例如：

5 2 2 5（表明有5个人，存在如下2对亲戚关系，问2和5是否为亲戚）

1 3

2 4

输出 NO

使用并查集来求解，首先定义一个大小为n的数组，表示有n个集合，亦表示n个人，如果两个人存在关系，

则合并对应的两个集合为一个集合，这里我们用一个集合（数组位）指向另一个集合（另一个数组位）来

表示集合的合并，比如：1和2存在关系，用array[2]=1，来表示2---->1，此表示方法可看成是树的结构，

有亲戚的人相连在一棵家族树上，所以对于一对亲戚关系，我们只需要找出其所在家族树的根节点，即可

判断他们是否是亲戚，若是亲戚则将其中一个的结点的头结点直接指向另外一个结点的头结点，则两棵树

上面的所有结点都互成为了亲戚。

 1 import java.util.Scanner;
 2 
 3 public class search {
 4     
 5     static int n;
 6     static int m;
 7     static int relation_one;
 8     static int relation_two;
 9     
10     static int find_Parent(int relation[],int jieDian) {    //寻找头结点
11         return jieDian==relation[jieDian]?jieDian:find_Parent(relation,relation[relation[jieDian]]);
12     }
13 
14     public static void main(String[] args) {
15         Scanner reader=new Scanner(System.in);
16         n=reader.nextInt();
17         m=reader.nextInt();
18         relation_one=reader.nextInt();
19         relation_two=reader.nextInt();
20         int relation[]=new int[n+1];    //编号1~n
21         for(int i=1;i<=n;i++) {    //初始指向自己
22             relation[i]=i;
23         }
24         
25         for(int i=1;i<=m;i++) {    //建树
26             int one=reader.nextInt();
27             int two=reader.nextInt();
28             int touOne=find_Parent(relation,one);    //寻找头结点
29             int touTwo=find_Parent(relation,two);
30             if(touOne!=touTwo) {    //非亲戚关系
31                 if(touOne<touTwo) {
32                     relation[touTwo]=touOne;    //相连成为亲戚,指向较小的
33                 }
34                 else {
35                     relation[touOne]=touTwo;
36                 }
37             }
38         }
39         
40         int result_one=find_Parent(relation,relation_one);
41         int result_two=find_Parent(relation,relation_two);
42         if(result_one==result_two) {
43             System.out.println("YES");
44         }
45         else {
46             System.out.println("NO");
47         }
48         
49     }
50 
51 }

View Code

10:09:52

2018-07-15