[type]UF

[Alice52]

• parent[index]=y: index 的父节点是 y

并查集

1. template

   class UF {
       // 连通分量个数
       private int count;
       // 存储一棵树
       private int[] parent;
       // 记录树的“重量”
       private int[] size;
   
       public UF(int n) {
           this.count = n;
           parent = new int[n];
           size = new int[n];
           for (int i = 0; i < n; i++) {
               parent[i] = i;
               size[i] = 1;
           }
       }
   
       public void union(int p, int q) {
           int rootP = find(p);
           int rootQ = find(q);
           if (rootP == rootQ)
               return;
   
           // 小树接到大树下面，较平衡
           if (size[rootP] > size[rootQ]) {
               parent[rootQ] = rootP;
               size[rootP] += size[rootQ];
           } else {
               parent[rootP] = rootQ;
               size[rootQ] += size[rootP];
           }
           count--;
       }
   
       public boolean connected(int p, int q) {
           int rootP = find(p);
           int rootQ = find(q);
           return rootP == rootQ;
       }
   
       private int find(int x) {
           while (parent[x] != x) {
               // 进行路径压缩
               parent[x] = parent[parent[x]];
               x = parent[x];
           }
           return x;
       }
   
       public int count() {
           return count;
       }
   }

list

1. 990--等式方程的可满足性
   • == 的连通 + != 若连通则错误