1. package com.example.suanfa.alg1;
    3. /**并查集使用
    4.  * @author lfy
    5.  * @date 2022-05-28
    6.  */
    7. public class BingChaCollection {
    10.     int[] fa,rank;
    11.     public void init(int n){
    12.         for (int i = 0; i < n; i++) {
    13.             fa[i] = i;
    14.             rank[i] = 1;
    15.         }
    16.     }
    17.     public int find(int x){
    18.         if (fa[x] == x){
    19.             return x;
    20.         }else {
    21.             return  find(fa[x]);
    22.         }
    23.         //return fa[x] == x ? x : find(fa[x]);
    24.     }
    26.     //树根据秩（节点的子树深度）进行合并，浅子树合并到深子树
    27.     public void merge(int i, int j)
    28.     {
    29.         int x = find(i), y = find(j);
    30.         if (rank[x] <= rank[y]){
    31.             fa[x] = y;}
    32.         else{
    33.             fa[y] = x;}
    34.         if (rank[x] == rank[y] && x != y){
    35.             rank[y]++;}
    36.     }
    38.     //亲戚问题，两个人的根节点只要在一个集合中，就说明有亲戚问题
    39.     public static void main(String[] args) {
    41.         //分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
    42.         int n=0, m=0, p=0, x=0, y=0;
    44.         BingChaCollection test = new BingChaCollection();
    45.         test.init(n);
    46.         for (int i = 0; i < m; ++i)
    47.         {
    48.             //scanf("%d%d", &x, &y);
    49.             test.merge(x, y);
    50.         }
    51.         for (int i = 0; i < p; ++i)
    52.         {
    53.             //scanf("%d%d", &x, &y);
    54.             System.out.println(test.find(x) == test.find(y) ? "Yes" : "No");
    55.         }
    57.     }
    59. }