Union Find

Last updated 2 years ago

Was this helpful?

Union Find

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)

  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;
    }

    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;
    }

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

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

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

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

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--;

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)).

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);         
        }
    }
}

public int removeStones(int[][] stones) {
    int numOfIslands = 0;
    int[] roots = new int[20000];
    for (int i = 0; i < roots.length; i++) {
        roots[i] = i;
    }
    for (int[] s : stones) {
        union(s[0], 10000 + 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;
}

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

nodes[root2].parent = root1;

nodes[root2].value = nodes[k1].value * values[i] / nodes[k2].value;

Iterate over queries:

Integer k1 = mIdTable.get(queries[i][0]);

Integer k2 = mIdTable.get(queries[i][1]);

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

else {

int root1 = find(nodes, k1);

int root2 = find(nodes, k2);

if (root1 != root2) result[i] = -1.0d;

else result[i] = nodes[k2].value / nodes[k1].value;

}

    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:

A node has more than one parents
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.

        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;
        }

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:

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

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

private void union(String one, String two) {

String p1 = find(one);

String p2 = find(two);

map.put(p1, p2);

}

循环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….];

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 非常精髓

FIND & UNION are different as typical:

private int find(int p, int[] A) {

return A[p];

}

private void union(int p, int q, int[] A) {

int rootP = find(p, A);

for (int i = 0; i < A.length; i++) {

if (A[i] == rootP) A[i] = find(q, A);

}

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

int time = 0;

while (!uf.isConnected(0, N * N - 1)) {

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

if (grid[i][j] > time) continue;

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

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

}

time++;

}

803. Bricks Falling When Hit

用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.

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

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

每一步都用UF的Size统计一下。

924. Minimize Malware Spread

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.

947. Most Stones Removed with Same Row or Column

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

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

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

Update PrimeToIndex: PrimeToIndex[p] = i

分到底了就break：

while (a % p == 0) a /= p;

if (a == 1) break;

用个HashMap来存PrimeToIndex：

Map<Integer, Set<Integer>> prime2Idx

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

for (int i = 0; i < N; i++) par[i] = i;

Arrays.fill(cnt, 1);

int max = 1;

for (Set<Integer> s : prime2Idx.values()) {

int fir = s.iterator().next();

for (int idx : s) {

union(idx, fir);

max = Math.max(cnt[find(idx)],max);

}

return max;

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

959. Regions Cut By Slashes

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

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一遍，找出不符合的” != “

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];

}

PreviousGraph NextTopological Sort

Last updated 2 years ago

Was this helpful?