Union-Find

题目套路

Union Find解决的最核心的问题就是集合合并以及Dynamic Connectivity, 所以题目一般都可以简化成Given a set of objects, connect two objects for a bunch of times, then ask if two objects are connected （graph里是否有环）or how many connected components are there? 这里我们需要确定的前提是connect表示的是undirected, or two directional 当用union-find 解决graph的问题时，我们要把图里的每个node理解为object，然后每个edge 相当于做了一次union operation。

Union-Find模板

  class UnionFind {
        HashMap<Integer, Integer> roots;
        int count;
        public UnionFind() {
            this.count = 0;
            this.roots = new HashMap<Integer, Integer>();
        }
        // add
        public void add(int num) {
            count++;
            roots.put(num, num);
        }
        // union
        public void union(int num1, int num2) {
            int root1 = root(num1);
            int root2 = root(num2);
            if (root1 == root2) {
                return;
            }
            roots.put(root1, root2);
            count--;
        }
        // find
        public boolean find(int num1, int num2) {
            return root(num1) == root(num2);
        }
        // root
        public int root(int num) {
            int temp = num;
            while (roots.get(num) != num) {
                num = roots.get(num);
            }
            int root = num;
            num = temp;
            while (roots.get(num) != num) {
                int parent = roots.get(num);
                roots.put(num, root);
                num = parent;
            }
            return root;
        }
    }

这里注意我们每次在考虑edge的find和union之前都要确保node已经add进去了。比如graph valid tree和find number of connected components in undirected graph这两道题，我们都要先把所有的node都add进去。因为题目只给了edges信息。而像number of islands 2这道题，我们只给了node信息，我们自然而然就先把node加进去，但是这时要check edge是否valid。

抽象化：寻找联通量

会在哪些情况下要求找connected components

在graph里面找connected components是关于graph的一个常见问题。具体可以用一个 矩阵来表示。

                  undirected      weak in directed        strong in directed

BFS             yes             no                      no

DFS             yes             no                      no

Union-Find      yes             yes                     no

所以可以看见，如果是无向图，那么这时候BFS/DFS都可以用，而且代码量比union-find 简单，所以杀鸡不用宰牛刀。但是如果是有向图求connected components，那么只有union-find可以求 weak connected components，而如果是strong connected components，都不可以。

还有一点，如果graph是变化的，比如总是有新的node连接起来（集合合并），那么哪怕是无向图，BFS/DFS 的time complexity也太高。这时一定要用union-find。所以对应到number of islands 2， matrix本质上是无向图，但是不断有集合合并，所以这时一定要用union-find。而number of islands 1，本质上就是在无向图里面求connected components，因为矩阵就是无向图， 而无向图每个node都可能是BFS的起点（seed），所以我们要遍历每一个点。所以总结下来， 所有的求connected components的问题都可以归为graph上的问题。

题目

• Leetcode 323. Number of Connected Components in an Undirected Graph
• Leetcode 261. Graph Valid Tree
• Leetcode 305. Number of Islands II