Union Find

Basic

Dynamic connectivity problems

• Unicon command: connect 2 obj
• Find/connected query, is there a path connecting the 2 obj (只能回答是不是，不能回答具体的路径）

Implementation the operations

• Find query: check if 2 objs are in the same component
• Union command: replace components containing 2 objects with their union

Quick-find

• find的时候直接比较，union的时候更新为所有有同样根的点O(n)
• defect：
  • union is expensive
  • trees are flat, but too expensive to keep them flat

Quick-union

• find和union的时候都找root，找到root以后，把root相连。（一直找往上找root，lazy approach, 引入 root func）
• Defect
  • Trees can get tall
  • Find too expensive (could be N array accesses)
• improve
  • Weighted quick-union
    • avoid tall tall trees by not putting large trees as lower tree. Tracking the objs in the tree and make sure to link the root of the smaller tree to root of larger tree. (Here is the union-by-size, not by height)
      • add size[] array to track the size, update it when union. union and connect both log(n)
  • path compression, 在计算（即 root 方程）完某个点的 root 之后，把所有 examined node 都指向 root, keep the tree almost completely flat
    • 两种实现方法
      • 在 root 中加上 second loop 来把所有 examined node的 root 设为 root
      • 直接把 path 中的所有点指向他的 grandparent id[i] = id[id[i]] (half the tree every time)
  • • 理论上非线性，实际上就是linear (iterative logN)
    • 实际操作中，在union里表面看仍然只是更新连接的点。但只要一旦call find不论是在connect还是union中，都会更新每个检查过的点，使得tree flat

一种解决集合(也有可能是单个点)查询和合并，支持O(1)Find和O(1)Union的数据结构, 这里的O(1)都是amortized

• 判断是否在同一个集合中: find O(1) after path compression
  • 理解在查询的时候，进行了压缩
• 合并集合 Union, 把a合并到b上
• UnionFind的派生操作
  • 检查当前集合中元素的个数size[]
  • 当前图中，集合的数量count

class UnionFind {
  private int[] father = null;

  public int find(int x) {
    if (father[x] == 0)
      return x;
    father[x] = find(father[x]);
    return father[x];
  }

  //iterative
  public int find(int x) {
      while (x != father[x]) {
          father[x] = father[father[x]];
          x = father[x];
      }
      return x;
  }

  public void union(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    if (root_a != root_b) 
      father[root_a] = root_b;
  }
}

Percolation

• 直接比较top line和bottom line的每一个点是否联通。O(n^2)
• 引入virtual top 和virtual bottom
• open site: 与相邻的四个点连接

Social Network

有 n 个点，m 次 connect 操作，最快什么时候联通(All connected)

• 这样 earliest/All 的问题可以视为以 UF 为 base 的算法的简单变形，只需要在理解，每一次connect时候先判断是否 connected，若为否，则进行 union，同时减少一个 count，当 count==1，即为全部联通
• 利用 count 来判断 earliest/All 是一个常用的方法

Connecting Graph

实现connect和query的API

• 用BFS/DFS可以发现，query需要O(n)
• 这时候就可以想到用UnionFind进行优化

Connecting Graph II

• 增加一个size数组来保存每个点的节点个数。在connect的时候，将root的size加上。在query的时候，记得返回的也是size(root_a)

public class ConnectingGraph2 { 

    private int[] father = null;
    private int[] size = null;

    private int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]);
    }

    public ConnectingGraph2(int n) {
        // initialize your data structure here.
        father = new int[n + 1];
        size = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public void connect(int a, int b) {
        // Write your code here
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
            size[root_b] += size[root_a];
        }
    }

    public int query(int a) {
        // Write your code here
        int root_a = find(a);
        return size[root_a];
    }
}

Connecting Graph III

判断总共连通块的个数，可以通过引入一个count，在connect时候如果有新的点连入(即root_a != root_b，则count--

[Graph Valid Tree](