> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/union-find.md).

# Union-Find & 2D matrix

## Key points

* 2D -> 1D, i\*cols + j
* **union find**

implementation: <http://blog.csdn.net/dm_vincent/article/details/7655764> <https://leetcode.com/problems/surrounded-regions/description/> <https://leetcode.com/problems/number-of-islands/> <https://leetcode.com/problems/number-of-islands-ii/description/>

dummy node:

* <https://leetcode.com/problems/surrounded-regions/description/>
* <https://leetcode.com/problems/bricks-falling-when-hit/discuss/121077/Java-Union-Find-by-backwardly-adding-bricks-back-20ms>

## Template

Example: <https://leetcode.com/problems/graph-valid-tree/description/>

```java
class Solution {
    public boolean validTree(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int i = 0; i < edges.length; i++) {
            if (uf.connected(edges[i][0],edges[i][1])) return false; // A cycle
            uf.union(edges[i][0],edges[i][1]);
        }
        return edges.length == n - 1;
    }
}

class UF {
    int[] father;
    int count;
    // All other parts are the same.
    // The difference is how to initialize UF.
    public UF(int n) {
        father = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    public void union(int p, int q) {
        int pFather = find(p);
        int qFather = find(q);
        if (pFather != qFather) {
            father[pFather] = qFather;
            count--;
        }
    }
    public int find(int p) {
        while (p != father[p]) p = father[p];
        return p;
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find (q);
    }
}
```

### Optimized: path compression, union by size weight.

```java
class UF {
    int[] father;
    int[] size;
    int count;
    // All other parts are the same.
    // The difference is how to initialize UF.
    public UF(int n) {
        count = n;
        father = new int[n];
        for (int i = 0; i < n; i++) father[i] = i;
        size = new int[n];
        for (int i = 0; i < n; i++) size[i] = 1;
    }
    public void union(int p, int q) {
        int pFather = find(p);
        int qFather = find(q);
        if (pFather == qFather) return;
        if (size[p] > size[q]) {
            father[qFather] = pFather;
        } else {
            father[pFather] = qFather;
        }
        count--;
    }

    // Path compression
    public int find(int p) {
        if (p != father[p]) {
            father[p] = find(father[p]);
        }
        return father[p];
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find (q);
    }
}
```

### String version

Use map to represent fathers.

* [734-Sentence Similarity](/leetcode/topics/union-find.md)
* <https://leetcode.com/problems/accounts-merge/description/>

```java
class UnionFind {
    Map<String, String> fathers = new HashMap<>();
    void connect(String s1, String s2) {
        fathers.putIfAbsent(s1, s1);
        fathers.putIfAbsent(s2, s2);

        String f1 = find(s1);
        String f2 = find(s2);
        if (!f1.equals(f2)) fathers.put(f1, f2);
    }
    String find(String s) {
        if (!fathers.get(s).equals(s)) {
            fathers.put(s, find(fathers.get(s)));
        }
        return fathers.get(s);
    }
}
```

### Detect cycle

Union the edges. If two vertex are already connected, then current edge will form a cycle.

* [684-Rredundant C-connection](/leetcode/topics/union-find.md)
* [685-Redundant Connection II](/leetcode/topics/union-find.md)

### Path finding

Node A, B connected: there is a path from A to B.

* [778. Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/)