什么是 union find(并查集) Link to heading

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题 — from Wikipedia

union find 适用于解决什么问题 Link to heading

给出节点, 判断他们是否联通, 并且不需要给出具体路径.

如果需要判断是否联通, 并且需要给出具体路径, 那么就需要用 BFS 或者 DFS 来解决了.

union find 的应用 Link to heading

  • 判断网络是否联通
  • lc 200, number of islands

Union find 设计 Link to heading

public class UF {
  // init n sites with integer names (0~n-1)
  UF(int n);
  // connect p and q
  void union(int p, int q);
  // find component id of p
  int find(int p);
  // return if p and q is connected
  boolean connected(int p, int q);
  // number of components
  int count();
}

union() 和 connected() 都依赖于 find(), 所以find()要很有效率才行.

quick union - union find 算法的一种实现 Link to heading

quick find 一种比较慢的算法 Link to heading

public class UF
{
  private int[] id; // access to component id (site indexed)
  private int count; // number of components
  public UF(int N)
  {
    // Initialize component id array.
    count = N;
    id = new int[N];
    for (int i = 0; i < N; i++)
      id[i] = i;
  }
  public int count()
  { return count; }
  public boolean connected(int p, int q)
  { return find(p) == find(q); }
  public int find(int p)
  { return id[p]; }
  public void union(int p, int q)
  {
    // 获得p和q的组号
    int pID = find(p);
    int qID = find(q);
    // 如果两个组号相等，直接返回
    if (pID == qID) return;
    // 遍历一次，改变组号使他们属于一个组, 这一步消耗巨大
    for (int i = 0; i < id.length; i++)
      if (id[i] == pID) id[i] = qID;
    count--;
  }
}

如果有 m 个新 union, 那么每次要遍历 n, 那么最后复杂度就成了 mn. 有没有办法不用这么复杂呢?

quick union 用树把相同组号的节点组织起来 Link to heading

quick union 和 quick find 的的差别就在 find 和 union 上.

public class UF
{
  private int[] id; // access to component id (site indexed)
  private int count; // number of components
  public UF(int N)
  {
    // Initialize component id array.
    count = N;
    id = new int[N];
    for (int i = 0; i < N; i++)
      id[i] = i;
  }
  public int count()
  { return count; }
  public boolean connected(int p, int q)
  { return find(p) == find(q); }
  private int find(int p)
  {
  	// 寻找p节点所在组的根节点，根节点具有性质id[root] = root
  	while (p != id[p]) p = id[p];
  	return p;
  }
  public void union(int p, int q)
  {
  	// Give p and q the same root.
  	int pRoot = find(p);
  	int qRoot = find(q);
  	if (pRoot == qRoot)
  		return;
  	id[pRoot] = qRoot;    // 将一颗树(即一个组)变成另外一课树(即一个组)的子树
  	count--;
  }
}

更多的优化 Link to heading

即使有 quick union, 但是在极端情况下, bst 会变成一个链表, 导致复杂度还是 mn.

为了克服这个问题, 我们可以把 bst 变成 avl或者红黑树.

如果树的大小不一样的话, 总把小的树并到大树上.

等等.

由于这个总结是为了更好地刷题, 所以想要了解更多, 还请参考原文.

credit to: Link to heading