Union Find

并查集是一种高效的数据结构，用于解决 连通问题、成环问题等。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }
    
    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }
    
    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

547. 省份数量

方法一：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    boolean[] visited;
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, res = 0;
        visited = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                bfs(i, isConnected, n);
                ++res;
            }
        }
        return res;
    }

    private void bfs(int i, int[][] isConnected, int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        visited[i] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int j = 0; j < n; ++j) {
                if (isConnected[node][j] == 1 && !visited[j]) {
                    visited[j] = true;
                    queue.offer(j);
                }
            }
        }
     }
}

方法二：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    boolean[] visited;
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, res = 0;
        visited = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(i, isConnected, n);
                ++res;
            }
        }
        return res;
    }

    private void dfs(int index, int[][] isConnected, int n) {
        visited[index] = true;
        for (int i = 0; i < n; ++i) {
            if (isConnected[index][i] == 1 && !visited[i]) {
                dfs(i, isConnected, n);
            }
        }
     }
}

方法三：并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length, res = n;
    parent = new int[n];
    for (int i = 0; i < n; ++i)
        parent[i] = i;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isConnected[i][j] == 1 && union(i, j))
                --res;
        }
    }
    return res;
}
int[] parent;
private boolean union(int i, int j) {
    int rootI = findParent(i), rootJ = findParent(j);
    if (rootI != rootJ) {
        parent[rootI] = rootJ;
        return true;
    }
    return false;
}

private int findParent(int i) {
    if (i != parent[i])
        parent[i] = findParent(parent[i]);
    return parent[i];
}

684. 冗余连接

方法一：并查集

  1. 初始化为森林，依次连接节点之间的边
  2. 如果连接边之前，节点不在同一个子集，那么合并
  3. 如果连接边之前，节点已经在同一个子集了，那么一定会形成环，这条边就是最后的冗余连接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        init(n + 1);
        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) {
                return edge;
            }
        }
        return new int[0];
    }
    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

1319. 连通网络的操作次数

方法一：并查集

  1. 找到连通分量

    1
    2
    3
    for (int i = 0 ; i < n ; i++)
        if (parent[i] == i)
            require++;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int makeConnected(int n, int[][] connections) {
        init(n);
        int redundancy = 0;
        for (int[] connection : connections) {
            if (!union(connection[0], connection[1])) { // 已连通
                ++redundancy;
            }
         }
        // 找到连通分量数，n个连通分量需要用n-1条边连接
        int require = -1;
        for (int i = 0 ; i < n ; i++)
            if (parent[i] == i)
                require++;
        if (require <= redundancy)
            return require;
        return -1;
    }
    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

面试题 16.19. 水域大小

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    boolean[][] visited;
    public int[] pondSizes(int[][] land) {
        int m = land.length, n = land[0].length;
        visited = new boolean[m][n];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!visited[i][j] && land[i][j] == 0) 
                    list.add(dfs(land, m, n, i, j));
            }
        }
        int[] res = list.stream().mapToInt(i->i).toArray();
        Arrays.sort(res);
        return res;
    }

    private int dfs(int[][] land, int m, int n, int i, int j) {
        visited[i][j] = true;
        int length = 1;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(m, n, row, col) && !visited[row][col] && land[row][col] == 0) {
                length += dfs(land, m, n, row, col);
            }
        }
        return length;
    }

    private boolean isValid(int m, int n, int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

方法二：并查集

  1. 使用哈希表count记录池塘的大小

  2. 初始化，额外将count赋值1

    1
    2
    3
    4
    5
    6
    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            count.put(i, 1);
        }

  3. 如果land[i][j] != 0，那么必然不会是池塘，将count值赋-1

    1
    2
    if (land[i][j] != 0)
       count.put(i * n + j, -1);

  4. 遍历依次合并，合并时将新parent的count加上被合并的count，并将被合并的parent的count赋值-1(便于收集结果)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            count.put(rootJ, count.get(rootI) + count.get(rootJ));
            count.put(rootI, -1);
            return true;
        }
        return false;
    }

  5. 收集结果

    1
    2
    3
    for (int val : count.values())
        if (val != -1)
            list.add(val);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    Map<Integer, Integer> count = new HashMap<>();
    public int[] pondSizes(int[][] land) {
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        int m = land.length, n = land[0].length;
        init(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] != 0)
                    count.put(i * n + j, -1);
                if (land[i][j] == 0) {
                    for (int[] dir : dirs) {
                        int row = i + dir[0], col = j + dir[1];
                        if (isValid(m, n, row, col) && land[row][col] == 0) {
                            union(i * n + j, row * n + col);
                        }
                    }
                }
            }
        }
//        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
//            System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
//        }
        List<Integer> list = new LinkedList<>();
        for (int val : count.values())
            if (val != -1)
                list.add(val);
        int[] res = list.stream().mapToInt(i->i).toArray();
        Arrays.sort(res);
        return res;
    }

    private boolean isValid(int m, int n, int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            count.put(rootJ, count.get(rootI) + count.get(rootJ));
            count.put(rootI, -1);
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            count.put(i, 1);
        }

    }
}

721. 账户合并

方法一：并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    Map<String, Integer> emailToId = new HashMap<>();
    Map<Integer, List<String>> idToEmail = new HashMap<>();
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        init(n);
        for (int i = 0; i < n; ++i) {
            int size = accounts.get(i).size();
            for (int j = 1; j < size; ++j) {
                String email = accounts.get(i).get(j);
                if (!emailToId.containsKey(email)) {
                    emailToId.put(email, i);
                }
                else {
                    union(i, emailToId.get(email));
                }
            }
        }
        for (String email : emailToId.keySet()) {
            int rootId = findParent(emailToId.get(email));
            List<String> emails = idToEmail.getOrDefault(rootId, new LinkedList<>());
            emails.add(email);
            idToEmail.put(rootId, emails);
        }
        // 加入name
        List<List<String>> res = new LinkedList<>();
        for (Map.Entry<Integer, List<String>> entry : idToEmail.entrySet()) {
            int id = entry.getKey();
            String name = accounts.get(id).get(0);
            List<String> row = new LinkedList<>();
            row.add(name);
            List<String> emails = entry.getValue();
            Collections.sort(emails);
            row.addAll(emails);
            res.add(row);
        }
        return res;
    }

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

剑指 Offer II 119. 最长连续序列

方法一：并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int longestConsecutive(int[] nums) {
        init(nums);
        Set<Integer> set = new HashSet<>();
        for (int x : nums)
            set.add(x);
        for (int x : nums) {
            if (set.contains(x - 1)) {
                union(x, x - 1);
            }
            if (set.contains(x + 1)) {
                union(x, x + 1);
            }
        }
        int res = 0;
        for (int cnt : count.values())
            res = Math.max(res, cnt);
        return res;
    }

    private void init(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            parent.put(nums[i], nums[i]);
            count.put(nums[i], 1);
        }
    }

    private int findParent(int num) {
        if (num != parent.get(num))
            parent.put(num, findParent(parent.get(num)));
        return parent.get(num);
    }

    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            count.put(rootI, count.get(rootI) + count.get(rootJ));
            parent.put(rootJ, rootI);
            return true;
        }
        return false;
    }

    Map<Integer, Integer> parent = new HashMap<>(), count = new HashMap<>();
}
Algorithms > Graph
#图 #并查集
Union Find
https://leopol1d.github.io/2023/05/29/union-find/
作者
Leopold
发布于
2023年5月29日
许可协议