摘要：并查集包括查詢和聯合，主要使用不相交集合查詢主要是用來決定不同的成員是否在一個子集合之內聯合主要是用來把多個子集合成一個集合的實際運用計算機網絡檢查集群是否聯通電路板檢查不同的電路元件是否聯通初始化聯通與檢測與是否聯通返回聯通的數

并查集(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...