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

# Union Find

#### [**323. Number of Connected Components in an Undirected Graph**](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)

n is the number of groups. When connect two node, reduce the number of groups, what left is result. 

*T: O(n^2) - O(n\*)  S: O(n)* 

{% tabs %}
{% tab title="Java" %}

```java
  public int countComponents(int n, int[][] edges) {
        int[] roots = new int[n];
        for (int i = 0; i < n; i++) roots[i] = i;
        for (int[] edge : edges) {
            int rootA = find(edge[0], roots);
            int rootB = find(edge[1], roots);
            if (rootA != rootB) {
                roots[rootA] = roots[rootB];
                n--;
            }
        }
        return n;
    }
    
    private int find(int p, int[] roots) {
        while (p != roots[p]) {
            roots[p] = roots[roots[p]];
            p = roots[p];
        }
        return p;
    }
```

{% endtab %}

{% tab title="Java BFS" %}

```java
    public int countComponents(int n, int[][] edges) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            map.putIfAbsent(edge[0], new HashSet<>());
            map.putIfAbsent(edge[1], new HashSet<>());
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        Set<Integer> visit = new HashSet<>();
        int count = 0;
        for (int i = 0; i < n ; i++) {
            if (visit.contains(i)) continue;
            Queue<Integer> q = new LinkedList<>();
            q.offer(i);
            visit.add(i);
            while (!q.isEmpty()) {
                int curt = q.poll();
                if (!map.containsKey(curt)) continue;
                for (int next : map.get(curt)) {
                    if (visit.contains(next)) continue;
                    visit.add(next);
                    q.offer(next);
                }
            }
            count++;
        }
        return count;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
def countComponents(self, n: int, edges: List[List[int]]) -> int:
    roots = [i for i in range(n)]
    for edge in edges:  
        # find
        rootU, rootV = self.find(edge[0], roots), self.find(edge[1], roots)
        # UNION
        if rootU != rootV:
            roots[rootU] = roots[rootV]
            n -= 1
    return n

def find(self, p, roots):
    while p != roots[p]:
        roots[p] = roots[roots[p]]
        p = roots[p]
    return p
```

{% endtab %}
{% endtabs %}

#### [547. Friend Circles](https://leetcode.com/problems/friend-circles/)

{% tabs %}
{% tab title="Java" %}

```python
    public int findCircleNum(int[][] M) {
        int n = M.length;
        int[] roots = new int[n];
        for (int i = 0; i < n; i++) roots[i] = i;
        int res = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int rootI = find(roots, i);
                int rootJ = find(roots, j);
                if (M[i][j] == 1 && rootI != rootJ) {
                    roots[rootI] = roots[rootJ];
                    res--;
                }
            }
        }
        return res;
    }
    
    private int find(int[] roots, int p) {
        while (p != roots[p]) {
            roots[p] = roots[roots[p]];
            p = roots[p];
        }
        return roots[p];
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
def findCircleNum(self, M: List[List[int]]) -> int:
    n = len(M)
    roots = [i for i in range(n)]
    res = n
    for i in range(n):
        for j in range(i + 1, n):
            rootU, rootV = self.find(i, roots), self.find(j, roots)
            if M[i][j] == 1:
                if rootU != rootV:
                    roots[rootU] = roots[rootV]
                    res -= 1
    return res

def find(self, p, roots):
    while p != roots[p]:
        roots[p] = roots[roots[p]]
        p = roots[p]
    return p
```

{% endtab %}
{% endtabs %}

#### [**261. Graph Valid Tree**](https://leetcode.com/submissions/detail/342253044/)

Valid Tree: 就是看有没有cycle, 找出每个点的Root，如果`if (rootX == rootY) return false`. 还要Check一下`edges.length == n - 1`。 有点像685. Redundant Connection II

```java
public boolean validTree(int n, int[][] edges) {
    if (edges == null) return false;
    int[] roots = new int[n];
    for (int i = 0; i < roots.length; i++) roots[i] = i;
    
    for (int[] edge : edges) {
        int rootP = find(edge[0], roots);
        int rootQ = find(edge[1], roots);
        if (rootP == rootQ) return false;
        roots[rootP] = roots[rootQ];
    }
    return edges.length == n - 1;
}

private int find(int p, int[] roots) {
    while (roots[p] != p) {
        roots[p] = roots[roots[p]];
        p = roots[p];
    }
    return roots[p];
}
```

#### **305. Number of Islands II**

很经典的题。主要要看2D matrix 和1D array的对应位置。是i \* width + j。

值得注意的是Count：

int count = results.isEmpty() ? 1 : results.get(results.size() - 1) + 1;

然后Union一次count--;

#### [947. Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/)

The stones on the same col and same row is an island, therefore actually this is a **number of islands** problem. The total number of stones minus the **"number of islands"** equals to the number of stones to remove. Therefore the problem becomes to find all connected number of islands. This can be achieved by DFS (O(n^2)) or UnionFind (O(n)).

{% tabs %}
{% tab title="DFS" %}

```java
public int removeStones(int[][] stones) {
    Set<int[]> visited = new HashSet<>();
    int numOfIslands = 0;
    for (int[] s : stones) {
        if (!visited.contains(s)) {
            dfs(s, visited, stones);
            numOfIslands++;
        }
    }
    return stones.length - numOfIslands;
}

private void dfs(int[] s, Set<int[]> visited, int[][] stones) {
    visited.add(s);
    for (int[] nextS : stones) {
        if (!visited.contains(nextS) && (s[0] == nextS[0] || s[1] == nextS[1])) {
            dfs(nextS, visited, stones);         
        }
    }
}
```

{% endtab %}

{% tab title="UnionFind" %}

```java
public int removeStones(int[][] stones) {
    int numOfIslands = 0;
    int[] roots = new int[200000];
    for (int i = 0; i < roots.length; i++) {
        roots[i] = i;
    }
    for (int[] s : stones) {
        union(s[0], 100000 + s[1], roots);
    }
    Set<Integer> rootsSet = new HashSet<>();
    for (int[] s : stones) {
        int root = find(s[0], roots);
        rootsSet.add(root);
    }
    return stones.length - rootsSet.size();
}

private void union(int A, int B, int[] roots) {
    int rootA = find(A, roots);
    int rootB = find(B, roots);
    roots[rootA] = roots[rootB];
}

private int find(int p, int[] roots) {
    while (p != roots[p]) {
        roots[p] = roots[roots[p]];
        p = roots[p];
    }
    return p;
}
```

{% endtab %}
{% endtabs %}

#### **399. Evaluate Division**

问a / b = 2.0, b / c = 3.0.

queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .

return \[6.0, 0.5, -1.0, 1.0, -1.0 ].

求出a, b, c作为分子和分母的关系

建一个Map\<String, Integer> 把每个Word和它的位置放进去。a:0, b:1, c:2

建len个Node用来做UF

Iterate over all words in equation, get roots of each node, set parent and value

&#x20;         `nodes[root2].parent = root1;`

&#x20;   `nodes[root2].value = nodes[k1].value * values[i] / nodes[k2].value;`

Iterate over queries:

&#x20;  `Integer k1 = mIdTable.get(queries[i][0]);`

&#x20;           `Integer k2 = mIdTable.get(queries[i][1]);`

&#x20;           `if (k1 == null || k2 == null) result[i] = -1.0d;`

&#x20;           `else {`

&#x20;               `int root1 = find(nodes, k1);`

&#x20;               `int root2 = find(nodes, k2);`

&#x20;               `if (root1 != root2) result[i] = -1.0d;`

&#x20;               `else result[i] = nodes[k2].value / nodes[k1].value;`

&#x20;           `}`\ <br>

#### [**684. Redundant Connection**](https://leetcode.com/problems/redundant-connection/)

```java
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] root = new int[n + 1];
        for (int i = 0; i <= n; i++) root[i] = i;
        
        for (int[] edge : edges) {
            int rootp = find(edge[0], root);
            int rootq = find(edge[1], root);
            if (rootp == rootq) return edge;
            root[rootp] = root[rootq];
        } 
        return new int[]{-1, -1};
    }
    
    private int find(int p, int[] root) {
        while (p != root[p]) {
            root[p] = root[root[p]];
            p = root[p];
        }
        return root[p];
    }
```

#### **685. Redundant Connection II**

Two cases to find redundant connection for directed graph:

1. A node has more than one parents
2. There is a loop

Therefore 2 candidates are needed. Can1 represents case1, can2 represents case2, else union. If both issues present, then the answer should be the first edge which results in "multiple parents" issue.

```java
        int[] can1 = null;
        int[] can2 = null;

        for (int[] edge : edges) {
            int rootU = find(edge[0] - 1, roots);
            int rootV = find(edge[1] - 1, roots);
            if (rootU != rootV) {
                if (rootV != edge[1] - 1) {
                    can1 = edge;
                } else {
                    roots[rootV] = rootU;
                }
            } else {
                can2 = edge;
            }
        }
        if (can1 == null) return can2;
        if (can2 == null) return can1;
        for (int[] edge : edges) {
            if (edge[1] == can1[1]) return edge;
        }
```

#### [**721. Accounts Merge**](https://leetcode.com/problems/accounts-merge/)

* UnionFind uf = new UnionFind(n);
* 建一个HashMap\<String, Integer>, 把所有的Email存进去: Value is Index. uf.union(preIndex, i) if preIndex is in map.
* 建一个HashMap\<Integer, Set\<String>> ufMap, store each index and its associated emails. This is by finding each individual roots and add value to its set.
* Convert and output result:

```java
public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> rootmap = new HashMap<>();
    UnionFind uf = new UnionFind(accounts.size());
    for (int i = 0; i < accounts.size(); i++) {
        for (int j = 1; j < accounts.get(i).size(); j++) {
            String email = accounts.get(i).get(j);
            if (rootmap.containsKey(email)) {
                uf.union(i, rootmap.get(email));
            } else {
                rootmap.put(email, i);
            }
        }
    }
    
    Map<Integer, Set<String>> map = new HashMap<>(); // index : email1 , email2
    for (int i = 0; i < accounts.size(); i++) {
        for (int j = 1; j < accounts.get(i).size(); j++) {
            int rootI = uf.find(i);
            map.putIfAbsent(rootI, new HashSet<>());
            map.get(rootI).add(accounts.get(i).get(j));
        }
    }
    
    List<List<String>> res = new ArrayList<>();
    for (int key : map.keySet()) {
        List<String> curt = new ArrayList<>(map.get(key));
        Collections.sort(curt);
        curt.add(0, accounts.get(key).get(0));
        res.add(curt);
    }
    return res;
}

class UnionFind {
    int[] roots;
    UnionFind(int N) {
        roots = new int[N];
        for (int i = 0; i < N; i++) roots[i] = i;
    }
    
    int find(int p) {
        while (p != roots[p]) {
            roots[p] = roots[roots[p]];
            p = roots[p];
        }
        return roots[p];
    }
    
    void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) roots[rootP] = roots[rootQ]; 
    }
}
```

#### [1061. Lexicographically Smallest Equivalent String](https://leetcode.com/problems/lexicographically-smallest-equivalent-string/)

```java
public String smallestEquivalentString(String A, String B, String S) {
    int[] graph = new int[26];
    for(int i = 0; i < 26; i++) {
        graph[i] = i;
    }
    for(int i = 0; i < A.length(); i++) {
        int a = A.charAt(i) - 'a';
        int b = B.charAt(i) - 'a';
        int end1 = find(graph, b);
        int end2 = find(graph, a);
        if(end1 < end2) {
            graph[end2] = end1;
        } else {
            graph[end1] = end2;
        }
    }
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < S.length(); i++) {
        char c = S.charAt(i);
        sb.append((char)('a' + find(graph, c - 'a')));
    }
    return sb.toString();
}

private int find(int[] graph, int idx) {
    while(graph[idx] != idx) {
        idx = graph[idx];
    }
    return idx;
}
```

#### **737. Sentence Similarity II**

**建一个HashMap, 把所有的Pair存进去，A:A and B:B, 并且Union A和B**

&#x20;   **private void union(String one, String two) {**

&#x20;       **String p1 = find(one);**

&#x20;       **String p2 = find(two);**

&#x20;       **map.put(p1, p2);**

&#x20;   **}**

**循环input array，如果有root不相等的直接return false;**

#### **765. Couples Holding Hands**

**row\.length : number of ppl, N = row\.length / 2: number of couples**

**Create an array to host relation: int\[] groups = new int\[row\.length];**

**Groups = \[0,0,1,1,2,2,3,3….];**<br>

**Get person1 and person 2, and couple1 = person1 / 2,  couple2 = person2 / 2**

**If couple1 != couple2, find roots of person, union person1 and person2, count swap++;**

**couple1 = person1 / 2 非常精髓**<br>

**FIND & UNION are different as typical:**

&#x20; **private int find(int p, int\[] A) {**

&#x20;   **return A\[p];**

&#x20; **}**<br>

&#x20; **private void union(int p, int q, int\[] A) {**

&#x20;   **int rootP = find(p, A);**

&#x20;   **for (int i = 0; i < A.length; i++) {**

&#x20;     **if (A\[i] == rootP) A\[i] = find(q, A);**

&#x20;   **}**

&#x20; **}**<br>

#### **778. Swim in Rising Water**

**BFS + PQ, DFS 都可以做。UF的这个非常精髓，尤其是!uf.isConnected(0, N \* N - 1)， 在不联通的情况下一直查找和Union，直到联通为止。**

**从2d到1d转换，new int\[N ^ 2], index from 0 to N ^ 2 - 1.**

**Origin:  i \* N + j**

**上下左右:**

* **Up:       i \* N - N + j**
* **Down:  i \* N + N + j**
* **Left:     i \* N + j - 1**
* **Right:   i \* N + j + 1**

&#x20; **int time = 0;**

&#x20;       **while (!uf.isConnected(0, N \* N - 1)) {**

&#x20;           **for (int i = 0; i < N; i++) {**

&#x20;               **for (int j = 0; j < N; j++) {**

&#x20;                   **if (grid\[i]\[j] > time) continue;**

&#x20;                   **if (i < N - 1 && grid\[i + 1]\[j] <= time) uf.union(i \* N + j, i \* N + j + N);**

&#x20;                   **if (j < N - 1 && grid\[i]\[j + 1] <= time) uf.union(i \* N + j, i \* N + j + 1);**

&#x20;               **}**

&#x20;           **}**

&#x20;           **time++;**

&#x20;       **}**<br>

#### **803. Bricks Falling When Hit**

[**解1**](https://leetcode.com/problems/bricks-falling-when-hit/solution/)**，** [**解2**](https://leetcode.com/problems/bricks-falling-when-hit/discuss/137465/Java-Union-Find-beats-100)

**用Size来统计每个砖联通多少砖**

**We'll also include dsu.top, which tells us the size of the "roof", or the component connected to the top edge. We use an ephemeral "source" node with label M \* N where all nodes on the top edge (with row number 0) are connected to the source node.**

**屋顶的问题很复杂，每找到一个点都要考虑是不是和屋顶链接。**<br>

**需要从后忘前算，先算最后hit的，然后一点一点往前。**

**先预处理，建UF的时候n要加1，把所有的点都Union到0。不管怎样，都要把四个方向的点都Union到Curt点上，还要加上Size。**[**（不用加四个方向，只管左和上就可以）**](https://leetcode.com/problems/bricks-falling-when-hit/discuss/137465/Java-Union-Find-beats-100)

**每一步都用UF的Size统计一下。**<br>

#### **924. Minimize Malware Spread**

```java
Iterate through all nodes, union i, j where node == 1
Initialize ‘count’ array to store root of each malware nodes, count[root]++
Iterate through initial, find root of each one, if count[root] == 1, refresh ans and ansSize by condition highlighted. RootSize > ansSize && rootSize == ansSize && node < ans

If ans = -1, assign ans as min of all nodes
  int[] count = new int[N];
        for (int node : initial) {
            count[uf.find(node)]++;
        }

        int ans = -1, ansSize = -1;
        for (int node : initial) {
            int root = uf.find(node);
            if (count[root] == 1) {
                int rootSize = uf.size(root);
                if (rootSize > ansSize || (rootSize == ansSize && node < ans)) {
                    ansSize = rootSize;
                    ans = node;
                }
            }
        }
```

#### **928. Minimize Malware Spread II**

**Ini a ‘clean’ array, set value to 0 if it is an initial, 1 if not an initial.**

**Iterate over nodes and union all nodes.**<br>

#### **947. Most Stones Removed with Same Row or Column**

```java
Union relation between i and j, use uf.union(stone[0], stone[1] + 10000), since
0 <= stones[i][j] < 10000.

Set a set and put in all roots of i. Return N - seen.size();

UF solution2:

   UnionFind uf = new UnionFind(stones);
        int total = stones.length;
        for(int[] stone: stones) {
            uf.union(stone[0], stone[1] + 10000);
        }
        return total - uf.getCount();
UF {
 for(int[] stone: stones) {
                int i = stone[0], j = stone[1];
                if(parents[i] == -1) count++;
                parents[i] = i;
                if(parents[j + 10000] == -1) count++;
                parents[j + 10000] = j + 10000;
            }
}
```

#### **952. Largest Component Size by Common Factor**

[**Solution 1**](https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/200546/Prime-Factorization-and-Union-Find) **Prime Factorization**

**先把所有100000以内的Prime number算出来**

**For A\[] 里面的每个数： 质数分解， A\[i] 除以p, 如果p在PrimeToIndex里，把Prime和A里面数的Index连上，Union(PrimeToIndex\[p], 和i)**

**Update PrimeToIndex:  PrimeToIndex\[p] = i**

**分到底了就break：**   &#x20;

&#x20;       **while (a % p == 0) a /= p;**

&#x20;               **if (a == 1) break;**<br>

[**Solution 2**](https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/200712/Fast-than-100-concise-java-solution)

**用个HashMap来存PrimeToIndex：**

**Map\<Integer, Set\<Integer>> prime2Idx**

**Map里存    质数：Array里所有可以用这个用质数分的数的Index**

&#x20;  **for (int i = 0; i < N; i++) par\[i] = i;**

&#x20;       **Arrays.fill(cnt, 1);**

&#x20;       **int max = 1;**

&#x20;       **for (Set\<Integer> s : prime2Idx.values()) {**

&#x20;           **int fir = s.iterator().next();**

&#x20;           **for (int idx : s) {**

&#x20;               **union(idx, fir);**

&#x20;               **max = Math.max(cnt\[find(idx)],max);**

&#x20;           **}**

&#x20;       **}**

&#x20;       **return max;**

**循环所有Map里的Values，Union所有的Index并同时取Max**<br>

#### **959. Regions Cut By Slashes**

[**Solution**](https://leetcode.com/problems/regions-cut-by-slashes/discuss/233278/Java-better-solution-with-Union-Find-100-\(time\))

**一个正方形是四个点，N \* N个点就要建立(N + 1) \* (N + 1)个点的UF array**

```java
If input is ‘ ’, we do nothing;
If input is ‘/’, we connect lower left vertex with upper right vertex;
If input is ‘\’, we connect upper left vertex with lower right vertex.

 for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                char op = grid[row].charAt(col);
                if (op == '/') {
                    if (uf.isConnected(row, col + 1, row + 1, col))
                        cnt += 1;
                    uf.union(row, col + 1, row + 1, col);
                } else if (op == '\\') {
                    if (uf.isConnected(row, col, row + 1, col + 1))
                        cnt += 1;
                    uf.union(row, col, row + 1, col + 1);
                }
            }
        }
```

#### **990. Satisfiability of Equality Equations**

**既然是找小写字母的关系，就建26位的Array，并Union如果是“==”的，再loop一遍，找出不符合的” != “**

```java
   int[] uf = new int[26];
    public boolean equationsPossible(String[] equations) {
        for (int i = 0; i < 26; ++i) uf[i] = i;
        for (String e : equations)
            if (e.charAt(1) == '=')
                uf[find(e.charAt(0) - 'a')] = find(e.charAt(3) - 'a');
        for (String e : equations)
            if (e.charAt(1) == '!' && find(e.charAt(0) - 'a') == find(e.charAt(3) - 'a'))
                return false;
        return true;
    }

    public int find(int x) {
        if (x != uf[x]) uf[x] = find(uf[x]);
        return uf[x];
    }
```