# 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];
    }
```


---

# 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://howardyangemail.gitbook.io/decode-leetcode/graph/union-find.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.