Union Find

Basics

Union/Find，并查集算法，通常用来解决动态连通性问题，即判断是否属于同一个group。 如果求具体路径，则需要用DFS来解决。

• Initially，新建一个 length = |V| 的数组或集合，并将每个 node 指向其本身，即构建 |V| 个独立的group。每个 index 代表一个 node，其 value 为 parent node。

• find(a, array) : 找到 array 中 a 的 root，即找到含 a 的 group 的头结点。

• union(a, b, array) : 将 a 和 b 连接起来。首先需要找到 a 和 b 所在 group 的头结点，若不相等，则将其中一个头结点指向另一个。

优化：其实上述算法实现的是Quick-Union。Find 和 Union 的时间复杂度跟树的高度有关，即 O(Tree Height) 。降低复杂度的方法，就是减少 Tree Height，那么当我们 union 的时候，应该将“小树“连到“大树“上，以尽量避免出现 unbalanced 的情况。这就是 Weighted Quick-Union。再进一步，如果我们能把一棵树做的足够扁平化，那么时间复杂度可以更少。这里引入路径压缩，即在找根节点的同时，将节点的父节点指向爷爷节点

Path Compression

主要函数

UF(int n)	initialize N sites with integer names (0 to N - 1)
int find(int p)	group identifier for p (0 to N - 1)
void union(int p, int q)	add connection between p and q
boolean connected(int p, int q)	return true if p and q are in the same group
int count()	number of groups

基本实现

Basic Implementation of Union/Find

不同 Union/Find 算法的时间复杂度

Algorithm	Constructor	Union	Find
Quick-Find	N	N	1
Quick-Union	N	Tree height	Tree height
Weighted Quick-Union	N	lgN	lgN
Weighted Quick-Union With Path Compression	N	Very near to 1 (amortized)	Very near to 1 (amortized)

Reference

并查集(Union-Find)算法介绍 : https://blog.csdn.net/dm_vincent/article/details/7655764

经典题目

200 Number of Islands 737 Sentence Similarity II

通常情况下以 array 作为底层数据结构，但遇到 String，Character 等类型时，可以利用 HashMap 映射。

200 Sol

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length;
        int m = grid[0].length;
        // initialize
        int[] array = new int[n*m];
        for (int i = 0; i < array.length; i++) {
            array[i] = -1;
        }
        int[][] dirs = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    int cur = i * m + j;
                    union(cur, cur, array);
                    for (int k = 0; k < dirs.length; k++) {
                        int neiRow = i + dirs[k][0];
                        int neiCol = j + dirs[k][1];
                        if (neiRow >= 0 && neiRow < n && neiCol >= 0 && neiCol < m && grid[neiRow][neiCol] == '1') {
                            int nei = neiRow * m + neiCol;
                            union(cur, nei, array);
                        }
                    }
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] != -1) {
                int head = find(i, array);
                set.add(head);
            }
        }
        return set.size();
    }
    
    private void union(int a, int b, int[] array) {
        int headA = find(a, array);
        int headB = find(b, array);
        if (headA != -1 && headB != -1) {
            array[headA] = headB;
        } else if (headA != -1 && headB == -1) {
            array[headA] = b;
        } else if (headA == -1 && headB != -1) {
            array[headB] = a;
        } else {
            array[a] = b;
        }
    }
    
    private int find(int num, int[] array) {
        if (array[num] == -1 || array[num] == num) return num;
        return find(array[num], array);
    }
}

737 Sol

class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        } 
        Map<String, String> map = getMap(pairs);
        // Union/Find
        for (int i = 0; i < words1.length; i++) {
            String w1 = words1[i];
            String w2 = words2[i];
            if (w1.equals(w2)) {        // rule 3
                continue;
            }
            String head1 = find(w1, map);
            String head2 = find(w2, map);
            if (head1 == null || head2 == null || !head1.equals(head2)) {
                return false;
            }
        }
        return true;
    }
    private String find(String w, Map<String, String> map) {
        if (!map.containsKey(w)) {
            return null;
        }
        if (map.get(w).equals(w)) return w;
        return find(map.get(w), map);
    }
    
    private void union(String w1, String w2, Map<String, String> map) {
        String head1 = find(w1, map);
        String head2 = find(w2, map);
        if (head1 == null && head2 == null) {
            map.put(w1, w1);
            map.put(w2, w1);
        } else if (head1 == null && head2 != null) {
            map.put(w1, head2);
        } else if (head1 != null && head2 == null) {
            map.put(w2, head1);
        } else {
            map.put(head1, head2);
        }
    }
}