题目背景

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

    题目描述

  • 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

    输入格式

  • 第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

  • 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。

  • 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

    输出格式

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

    解题思路

  • 并查集：将亲戚与亲戚之间进行按秩合并，采用路径压缩的方式在查找时将父节点设置为根节点 ```java import java.util.Scanner; public class Disjoint_Set_Union { private final static Integer MAX_LEN = 8192; // 并查集中的父（根）节点集合 private static Integer[]fa = new Integer[MAX_LEN]; // 并查集中的秩 private static Integer[]rank = new Integer[MAX_LEN];

    // 初始化 public static void init(int n){

    1.  for (int i = 1; i < n; i++) {
    2.      fa[i] = i;
    3.      rank[i] = 1;
    4.  }

    } // 查询-路径压缩 public static int find(int x){

    1.  return x == fa[x] ? x : (fa[x] = find(fa[x]));

    }

    // 合并-非秩 public static void merge(int x,int y){

    1.  fa[x] = find(fa[y]);

    }

    // 合并-秩 public static void rank_merge(int x,int y){

    1.   int i = find(x);
    2.   int j = find(y);
    3.   if (rank[i] <= rank[j]){
    4.       fa[i] = find(fa[j]);
    5.   }else{
    6.       fa[j] = find(fa[i]);
    7.   }
    8.   if (rank[i] == rank[j] && i != j){
    9.       rank[j]++;
    10.   }

    }

    public static void main(String[] args) {

     Scanner sc = new Scanner(System.in);
 int n = sc.nextInt();
 int m = sc.nextInt();
 int p = sc.nextInt();
 // 初始化
 init(n);
 for (int i = 0; i < m; i++) {
     int m1 = sc.nextInt();
     int m2 = sc.nextInt();
     // 合并亲戚
     //merge(m1,m2);
     rank_merge(m1,m2);
 }

 for (int i = 0; i < p; i++) {
     int p1 = sc.nextInt();
     int p2 = sc.nextInt();
     // 查找亲戚
     if (find(p1) == find(p2)){
         System.out.println("Yes");
     }else {
         System.out.println("No");
     }
 }

    } }

```