Leetcode之Union-Find(并查集)

摘要：并查集包括查询和联合，主要使用不相交集合查询主要是用来决定不同的成员是否在一个子集合之内联合主要是用来把多个子集合成一个集合的实际运用计算机网络检查集群是否联通电路板检查不同的电路元件是否联通初始化联通与检测与是否联通返回联通的数

并查集(Union-Find)包括查询(Find)和联合(Union)，主要使用不相交集合(Disjoint-Sets)
查询(Find)主要是用来决定不同的成员是否在一个子集合之内
联合(Union)主要是用来把多个子集合成一个集合
Union-Find的实际运用：
1.计算机网络检查集群是否联通 2.电路板检查不同的电路元件是否联通

Union-Find(mainly used for detection of connectivity problem):

Public Class UF:
    UF(int n) //初始化(abstract N sites : list of integers to 0,1,2 .. N-1)
    Void Union(int a, int b) //联通a与b(add connection between a and b)
    int find(int a) //component identifier
    boolean isConnected(int a, int b) //检测a与b是否联通
    int count() //返回联通的数量(return number of connected components)

举个例子：
Given Objects: 0, 1, 2, 3, 4, 5
union(0, 1):
0-1, 2, 3, 4, 5
union(1,3):
0-1-3, 2, 4, 5
union(2,5):
0-1-3, 2-5, 4
union(3, 5):
0-1-3-2-5, 4

Union-Find在计算机算法面试主要用来解决动态图(Dynamic Graph)的一系列问题:
例如： 一个由0与1组成的二维矩阵，0可以看成海洋，1可以看成陆地
110101
001011
101011
100110
Q1:有多少岛？4(dfs,bfs),静态图(static graph)
Q2:湖(上下左右不包换对角线被陆地包围)的面积有多少? 2(dfs, bfs),静态图
Q3:如果改变图中的元素有多少岛?(0,0):5; (0,1):5; (0, 5): 6; (1,5): 5, 动态图(Dynamic Graph)

Union-Find的种类：
Quick UnionFind(Quick-Union)

class QuickUnion:
    private int[] ids;
    public QuickUnionFind(int n):
        ids = new int[n];
        for(int i = 0; i < n; i++) {
            ids[i] = i;
        }
    }
    public void union(int a, int b) {
        int idA = ids[a];
        int idB = ids[b];
        for(int i = 0; i < n; i++) {
            if(ids[i] == idB){ //联通所有与A联通的元素
                ids[i] = idA;
            }
        }
    }
    public boolean find(int a, int b) {
        return ids[a] == ids[b];
    }
 }

比如，如果想要连通id[5]与id[9], 需要在union的过程中遍历所有与id5连通的元素将下标改成id9，或者将所有id9的下标改成id5

QuickUnion的遍历需要通过一次的数组读取来找到对应的节点，但是对于新增路径需要需要线性时间找到对应的组号进行修改，所以对于大数据量来说如果新增路径数量是M，节点的数量是N，我们需要O(MN)的时间复杂度来寻找对应的标号然后修改，平方的时间复杂度是非常费时的，所以我们需要提高Union的效率

Tree Union Find
QuickUnion之所以Union的时间复杂度比较高主要是因为对于每个节点的所属的组都是多带带记录，因此需要一种更优化的数据结构来快速更新节点所属的组，因此我们可以用一个parent node来连接所有的sub node形成树来降低Union的时间

使用parent-link将子节点与根节点连接，id[a]的值就是父节点的序号，因此通过查找，总可以从一个子节点查找到根节点(id[a] == a)，因此在处理不同组的时候，我们只需要找到每个元素的根节点然后更新根节点的指向就可以了，就相当于将其中一个根节点所代表的树变成另外一个根节点的子树

class TreeUnionFind:
    private int[] ids;
    public TreeUnionFind(int n) {
        ids = new int[n];
        for(int i = 0; i < n; i++) {
            ids[i] = i;
        }
    }
    public int root(int a) {
        int root = a;
        while(ids[root] != root) {
                ids[root] = root;
        }
    }
    public boolean find(int a, int b) {
        return root(a) == root(b);
    }
    public void union(int a, int b) {
        int rootA = ids[a];
        int rootB = ids[b];
        ids[rootA] = rootB;
    }
}

但是树这种数据结果经常会根据输入数据本身的性质而变化，如果输入数据是有序的相对应的树会变成一个单一链表因而不具备范性的运用情况

Weighted Quick Union Find

根据Quick-Union Find:

    public void union(int a, int b) {
        int idA = ids[a];
        int idB = ids[b];
        for(int i = 0; i < n; i++) {
            if(ids[i] == idB){ 
                ids[i] = idA;
            }
        }
    }

ids[i] = idA是一种hard code的习惯，因为random assign一棵树是另外一棵树的子树没有考虑输入数据的规模，如果输入数据p与q， 如果p数据所在树的规模比q数据所在树的规模大得多，p与q新形成的树不是平衡树

因此，需要总是需要用小的size的树与大的size的树合并从而尽量达到树的平衡

class WeightedQuickUnionFind{
    private int[] ids;
    private int[] sizes;
    public WeightedQuickUnionFind(int n) {
        ids = new int[n];
        sizes = new int[n]; //在quickUnion的基础上增加一个记录size的变量
        for(int i = 0; i < n; i++) {
            ids[i] = i;
            sizes[i] = 1;//初始化size的大小为1
        }
    }
    public int root(int a, int b) {
        int root = a;
        while(ids[root] != root) {
            root = ids[root];
        }
        return root;
    }
    public void union(int a, int b) {
        int rootA = ids[a];
        int rootB = ids[b];
        if(sizes[rootA] > sizes[rootB]) { //判断size的大小来更新root
            ids[rootB] = rootA;
            sizes[rootA] += sizes[rootB];
        } else {
            ids[rootA] = rootB;
            sizes[rootB] += sizes[rootA];
        } 
    }
 }        

通过weightedQuickUnion, 可以通过O(logn)的时间复杂度来分别Union和Find所需要的元素

Weighted QuickUnion With Path Compression
在Weighted QuickUnion的基础上我们可以通过路径压缩(path compression)就是把所有的元素下标直接连接到父节点来达到降低Union和Find时间复杂度的目的

class weightedQuickUnionWithPathCompression{
    private int[] ids;
    private int[] sizes;
    public weightedQuickUnionWithPathCompression(int n) {
        ids = new int[n];
        sizes = new int[n];
        for(int i = 0; i < n; i++) {
            ids[i] = i;
            sizes[i] = 1;
        }
    }
    public int root(int a, int b) {
        int root = a;
        while(ids[root] != root) {
            root = ids[root];
        }
        while(a != root) { //connect sub element directly to root
            int temp = ids[a];
            ids[a] = root;
            a = temp;
        }
        return root;
    }
    public boolean find(int a, int b) {
        return root(a) == root(b);
    }
    public boolean union(int a, int b) {
        int rootA = ids[a];
        int rootB = ids[b];
        if(sizes[rootA] > sizes[rootB]) {
            ids[rootB] = rootA;
            sizes[rootA] += sizes[rootB];
        } else {
            ids[rootA] = ids[rootB];
            sizes[rootB] += sizes[rootA];
        }
    }
 }

由此，以上就是所有关于动态连接的UnionFind的介绍，下图是不同思路并查集的算法时间复杂度对比：
Algorithm
Quick UnionFind: Construct: O(n); Find: O(1); Union:O(n)
Tree UnionFind: Construct: O(n); Find: O(tree height); Union:O(n)
Weighted QuickUnionFind:Construct: O(n); Find: O(logn); Union:O(logn)
Weighted QuickUnionFind with Path Compression: Construct: O(n); Find: amortizedO(1); Union:amortizedO(1)

leetcode里使用UnionFind的题主要有:Number of Islands(lc200), LongestConsecutiveSequence(lc128), SurroundedRegion(lc130)

Surrounded Region:
Given a 2D board containing "X" and "O" (the letter O), capture all regions surrounded by "X".A region is captured by flipping all "O"s into "X"s in that surrounded region.
For Example:
XXXX
XOOX
XXOX
XOXX
After should become:
XXXX
XXXX
XXXX
XOXX

class Solution{
    public void solve(char[][] board) {
        //sanity check
        if(board == null || board.length == 0) return;
        int row = board.length;
        int col = board[0].length;
        int dummy = row * col; //create a dummy node to represent list of nodes
        UnionFind uf = new UnionFind(row * col + 1);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(board[i][j] == "O") {
                    if(i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                        uf.union(node(i, j), dummy); //connect corner nodes
                    } else {
                        if(i > 0 && board[i-1][j] == "O") uf.union(node(i, j), node(i-1, j));
                        if(i > 0 && board[i+1][j] == "O") uf.union(node(i, j), node(i-1, j));
                        if(j > 0 && board[i][j-1] == "O") uf.union(node(i, j), node(i, j-1));
                        if(j > 0 && board[i][j+1] == "O") uf.union(node(i, j), node(i, j+1));
                    }
                }
            }
         }
         for(int i = 0; i < row; i++) {
             for(int j = 0; j < col; j++) {
                 if(uf.isConnected(board[i][j], dummy)) board[i][j] = "O";
                 else board[i][j] = "X";
             }
         }
      }
      public int node(int i, int j) {
          return i * col + j;//convert 2d dimension to 1d
      }
 }
 class UnionFind{
     int[] parents;
     public UnionFind(int[] n) {
         parents = new int[n];
         for(int i = 0; i < n; i++) {
             parents[i] = i;
         }
     }
     public void union(int i, int j) {
         int rootA = find(i);
         int rootB = find(j);
         if(rootA != rootB) {
             parents[rootA] = rootB;
         }
     }
     public int find(int node) {
         if(parents[node] == node) return node;
         parents[node] = find(parents[node]);
         return parents[node];
     }
     public boolean isConnected(int n1, int n2) {
         return find(n1) == find(n2);
     }
}

References:
1.https://algs4.cs.princeton.ed...

2.http://blog.csdn.net/dm_vince...