摘要：不得不說(shuō)，對(duì)于這道題而言，是一種很木訥的模板。主函數(shù)按矩陣大小建立一個(gè)類(lèi)進(jìn)行后續(xù)操作一個(gè)結(jié)點(diǎn)用來(lái)連接邊角不可能被圍繞的一個(gè)函數(shù)對(duì)矩陣元素進(jìn)行結(jié)點(diǎn)線性化。同理，，，在主函數(shù)中初始化后調(diào)用。

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,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

不得不說(shuō)，對(duì)于這道題而言，Union Find是一種很木訥的模板。

主函數(shù)：按矩陣大小建立：

一個(gè)UnionFind類(lèi)進(jìn)行后續(xù)操作；

一個(gè)dummy結(jié)點(diǎn)用來(lái)連接邊角不可能被X圍繞的O；

一個(gè)node()函數(shù)對(duì)矩陣元素進(jìn)行結(jié)點(diǎn)線性化。

操作：

遍歷所有結(jié)點(diǎn)，矩陣邊角的O與dummy相連，矩陣內(nèi)部的O與相鄰的O相連；

遍歷所有結(jié)點(diǎn)，與dummy相連的結(jié)點(diǎn)設(shè)置為O，其它所有結(jié)點(diǎn)設(shè)置為X。

UnionFind函數(shù)：建立：

全局變量parents；

初始化函數(shù)UnionFind(int size)；

查找parents函數(shù)find(int node)；

歸并函數(shù)union(int node1, int node2)；

測(cè)試兩結(jié)點(diǎn)是否相連函數(shù)isConnected(int node1, int node2)；

操作：

find(int node): 用while循環(huán)向上查找node的parent，注意先向上迭代parents[node]，再迭代node，否則會(huì)超時(shí)；

union(int node1, int node2): 找到兩個(gè)結(jié)點(diǎn)的parents，r1和r2，令parents[r1] = r2；

isConnected(int n1, int n2): 查看兩個(gè)結(jié)點(diǎn)的parents是否相等。

public class Solution {
    int row, col;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        row = board.length;
        col = board[0].length;
        UnionFind uf = new UnionFind(row*col+1);
        int dummy = row*col;
        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);
                    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(node(i, j), dummy)) board[i][j] = "O";
                else board[i][j] = "X";
            }
        }
    }
    public int node(int i, int j) {
        return i*col+j;
    }
}

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 n1, int n2) {
        int r1 = find(n1);
        int r2 = find(n2);
        if (r1 != r2) parents[r1] = r2;
    }
    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);
    }
}

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

同理，find，union，在主函數(shù)中初始化后調(diào)用。

public class Solution {
    int[] parents;
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n-1) return false;
        parents = new int[n];
        for (int i = 0; i < n; i++) parents[i] = i;
        for (int i = 0; i < n-1; i++) {
            if (find(edges[i][0]) == find(edges[i][1])) return false;
            union(edges[i][0], edges[i][1]);
        }
        return true;
    }
    public int find(int n) {
        if (parents[n] == n) return n;
        parents[n] = find(parents[n]);
        return parents[n];
    }
    public void union(int n1, int n2) {
        int r1 = find(n1);
        int r2 = find(n2);
        if (r1 != r2) parents[r1] = r2;
    }
}

Given a 2d grid map of "1"s (land) and "0"s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

public class Solution {

    class UnionFind {
        public int count;
        public int[] parents;
        public UnionFind(int m, int n, char[][] grid) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == "1") count++;
                }
            }
            parents = new int[m*n];
            for (int i = 0; i < m*n; i++) parents[i] = i;
        }
        public int find(int i) {
            if (i == parents[i]) return i;
            parents[i] = find(parents[i]);
            return parents[i];
        }
        public void union(int i, int j) {
            int pi = find(i);
            int pj = find(j);
            if (pi == pj) return;
            else parents[pi] = pj;
            count--;
        }
        public boolean isConnected(int i, int j) {
            return find(i) == find(j);
        }
    }
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(m, n, grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == "0") continue;
                int x = i*n+j;
                int y;
                if (i < m-1 && grid[i+1][j] == "1") {
                    y = x+n;
                    uf.union(x, y);
                }
                if (j < n-1 && grid[i][j+1] == "1") {
                    y = x+1;
                    uf.union(x, y);
                }
            }
        }
        return uf.count;
    }
}