# Union-Find, 并查集应用

### [Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/)

* **开始做题之前，要注意先把定义和可能的各种 test case 正确输出弄清楚。在 LeetCode 上就只能反复提交试错，但是面试的时候，做题之前这些都是要通过交流去问清楚的，要么后面会浪费很多时间去涂涂改改，甚至发现一开始就答错了。。**

给定一个 Set of Nodes ，Tree 要满足两个条件：

* 无环
* 单 root 节点

![](/files/-MUt7bfOcb2IugZXOGQV)

把这两点搞清楚之后，这题就很简单了。先一个一个 edge 去加，如果发现有环的话直接返回 false；否则跑到最后，看看最终的 number of connected components 是不是 1.

```java
public class Solution {
    private class WeightedUnionFind{
        HashMap<Integer, Integer> parent;
        HashMap<Integer, Integer> size;
        boolean hasCycle;
        int count;

        public WeightedUnionFind(int n){
            parent = new HashMap<Integer, Integer>();
            size = new HashMap<Integer, Integer>();
            hasCycle = false;
            count = n;

            for(int i = 0; i < n; i++){
                parent.put(i, i);
                size.put(i, 1);
            }
        }

        public Integer find(Integer node){
            if(!parent.containsKey(node)) return null;
            Integer root = node;
            while(root != parent.get(root)){
                root = parent.get(root);
            }
            while(node != root){
                Integer next = parent.get(node);
                parent.put(node, root);
                node = next;
            }
            return root;
        }

        public void union(Integer nodeA, Integer nodeB){
            Integer rootA = find(nodeA);
            Integer rootB = find(nodeB);
            if(rootA == null || rootB == null) return;
            if(rootA.equals(rootB)) {
                hasCycle = true;
                return;
            }

            int sizeA = size.get(rootA);
            int sizeB = size.get(rootB);

            if(sizeA > sizeB){
                parent.put(rootB, rootA);
                size.put(rootA, sizeA + sizeB);
            } else {
                parent.put(rootA, rootB);
                size.put(rootB, sizeA + sizeB);
            }
            count --;
        }

        public boolean hasCycle(){
            return this.hasCycle;
        }

        public boolean isTree(){
            return (!this.hasCycle) && (count == 1);
        }

    }

    public boolean validTree(int n, int[][] edges) {
        if(edges == null || edges.length == 0){
            if(n > 1) return false;
            else return true;
        }

        WeightedUnionFind uf = new WeightedUnionFind(n);

        for(int i = 0; i < edges.length; i++){
            int nodeA = edges[i][0];
            int nodeB = edges[i][1];
            uf.union(nodeA, nodeB);
            if(uf.hasCycle()) return false;
        }

        return uf.isTree();
    }
}
```

### [Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)

第一次写的时候用了个 HashSet 记录哪些点访问过，显得麻烦，还浪费了额外空间。

* **这种在矩阵上做 flood filling 的问题，可以靠自定义字符做标记，取代用额外空间的记录方式。**

这段代码的逻辑就是从四个边开始碰到 'O' 就往里扫，把扫到的都标上 'S' 代表有效湖；最后过一遍的时候除了 'S' 的都标成 'X' 就好了。

然而在大矩阵上 stackoverflow\... 看来无脑 dfs 的做法还不够经济啊。。。

```java
public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;

        for(int i = 0; i < cols; i++){
            if(board[0][i] == 'O'){
                dfs(board, 0, i);
            }
            if(board[rows - 1][i] == 'O'){
                dfs(board, rows - 1, i);
            }
        }

        for(int i = 1; i < rows - 1; i++){
            if(board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            if(board[i][cols - 1] == 'O'){
                dfs(board, i, cols - 1);
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] == 'S'){
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void dfs(char[][] board, int row, int col){
        if(row < 0 || row >= board.length) return;
        if(col < 0 || col >= board[0].length) return;
        if(board[row][col] != 'O') return;

        board[row][col] = 'S';

        dfs(board, row + 1, col);
        dfs(board, row - 1, col);
        dfs(board, row, col + 1);
        dfs(board, row, col - 1);
    }
}
```

写了个 BFS 的在一个中型矩阵上 TLE了，我有点方。。

```java
public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = 0; i < cols; i++){
            if(board[0][i] == 'O'){
                queue.offer(i);
                bfs(board, 0, i, queue);
            }
            if(board[rows - 1][i] == 'O'){
                queue.offer((rows - 1) * cols + i);
                bfs(board, rows - 1, i, queue);
            }
        }

        for(int i = 1; i < rows - 1; i++){
            if(board[i][0] == 'O'){
                queue.offer(i * cols);
                bfs(board, i, 0, queue);
            }
            if(board[i][cols - 1] == 'O'){
                queue.offer(i * cols + cols - 1);
                bfs(board, i, cols - 1, queue);
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] == 'S'){
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void bfs(char[][] board, int row, int col, Queue<Integer> queue){
        int rows = board.length;
        int cols = board[0].length;

        if(!isValid(row, rows, col, cols)) return;

        while(!queue.isEmpty()){
            Integer index = queue.poll();
            int x = index / cols;
            int y = index % cols;
            if(board[x][y] == 'O') board[x][y] = 'S';

            if(isValid(x + 1, rows, y, cols) && board[x + 1][y] == 'O') queue.offer((x + 1) * cols + y);
            if(isValid(x - 1, rows, y, cols) && board[x - 1][y] == 'O') queue.offer((x - 1) * cols + y);
            if(isValid(x, rows, y + 1, cols) && board[x][y + 1] == 'O') queue.offer(x * cols + y + 1);
            if(isValid(x, rows, y - 1, cols) && board[x][y - 1] == 'O') queue.offer(x * cols + y - 1);
        }

        return;
    }

    private boolean isValid(int row, int rows, int col, int cols){
        if(row < 0 || row >= rows) return false;
        if(col < 0 || col >= cols) return false;
        return true;
    }
}
```

同样的 DFS 逻辑，做了如下改动之后就不会 stackoverflow 了：

* DFS 时不进入最外围一圈的位置

简单来讲是在尽可能限制 DFS call stack 的层数，控制 DFS 的深度。从正确性上讲，上面的写法也是正确的，但是在极端情况下如果某一个从边沿出发的 DFS 连通了另一个边沿出发的 DFS，会导致一次的搜索路径非常长，于是 stackoverflow. 既然边沿的格子无论如何都要检查一遍，就把外圈封住，减少每个起点的 search tree depth.

```java
public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int rows = board.length;
        int cols = board[0].length;

        for(int i = 0; i < cols; i++){
            if(board[0][i] == 'O'){
                dfs(board, 0, i);
            }
            if(board[rows - 1][i] == 'O'){
                dfs(board, rows - 1, i);
            }
        }

        for(int i = 1; i < rows - 1; i++){
            if(board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            if(board[i][cols - 1] == 'O'){
                dfs(board, i, cols - 1);
            }
        }

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] == 'S'){
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void dfs(char[][] board, int row, int col){
        if(row < 0 || row >= board.length) return;
        if(col < 0 || col >= board[0].length) return;

        if(board[row][col] != 'O') return;

        board[row][col] = 'S';

        // DFS 时不进入最外圈
        if(row + 2 < board.length && board[row + 1][col] == 'O') dfs(board, row + 1, col);
        if(row - 2 >= 0 && board[row - 1][col] == 'O') dfs(board, row - 1, col);
        if(col + 2 < board[0].length && board[row][col + 1] == 'O') dfs(board, row, col + 1);
        if(col - 2 >= 0 && board[row][col - 1] == 'O') dfs(board, row, col - 1);
    }
}
```

这题当然也可以用 Union-Find 写，先把所有最外圈的 boundry 连上，然后把里面的相邻 'O' 做 union，最后扫矩阵的时候，如果对应的 root 不是 boundry root 就留下，不然都改成 'X'.

不过只是在这个问题上，不是很简洁。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/union-findff0c_bing_cha_ji/67-_union-find-_bing_cha_ji_ying_yong.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.