1. //并查集模板
    2. class UF {
    3.     int count;
    4.     int[] size;
    5.     int[] parent;
    6.     public UF(int n) {
    7.         this.count = n;
    8.         this.size = new int[n];
    9.         this.parent = new int[n];
    10.         for (int i=0; i<n; i++) {
    11.             parent[i] = i;
    12.             size[i] = 1;
    13.         }
    14.     }
    16.     public int find(int x) {
    17.         while (parent[x] != x) {
    18.             parent[x] = parent[parent[x]];
    19.             x = parent[x];
    20.         }
    21.         return x;
    22.     }
    24.     public void union(int p, int q) {
    25.         int rootP = find(p);
    26.         int rootQ = find(q);
    27.         if (rootP == rootQ) {
    28.             return;
    29.         }
    30.         if (size[rootP] > size[rootQ]) {
    31.             parent[rootQ] = rootP;
    32.             size[rootP] += size[rootQ];
    33.         } else {
    34.             parent[rootP] = rootQ;
    35.             size[rootQ] += size[rootP];
    36.         }
    37.         this.count--;
    38.     }
    40.     public boolean isConnect(int p, int q) {
    41.         int rootP = find(p);
    42.         int rootQ = find(q);
    43.         return rootP == rootQ;
    44.     }
    45. }