IVN
0%

UnionFind

Posted on Edited on In
Symbols count in article: 32k Reading time ≈ 29 mins.

Union Find选编

并查集被很多OIer认为是最简洁而优雅的数据结构之一，并查集算法通常用在处理一些不交集（Disjoint Sets）的合并及查询问题，并支持两种操作：

  • 合并（Union）：把两个不相交的集合合并为一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

547. Number of Provinces

江湖上有多少帮派？

java并查集算法讲解 - 编程宝库 (codebaoku.com)

基础版本：

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
public class LeetCode547 {
    public int findCircleNum(int[][] isConnected) {
        int n=isConnected.length;
        UnionFind u=new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if(isConnected[i][j]==1){
                    u.union(i,j);
                }
            }
        }

        return u.total;
    }

    class UnionFind{
        int[] parents;
        int[] sizes;
        int total;
        UnionFind(int n){
            parents=new int[n];
            sizes=new int[n];
            for (int i = 0; i < n; i++) {
                parents[i]=i;
                sizes[i]=1;
            }
            total=n;
        }

        int find(int i){
            while(i!=parents[i]){
                i=parents[i];
            }
            return i;
        }

        void union(int a, int b){
            int pA=find(a);
            int pB=find(b);
            if(pA==pB){
                return;
            }
            total--;
            if(sizes[pA]>=sizes[pB]){
                parents[pB]=pA;
                sizes[pA]+=sizes[pB];
            }else{
                parents[pA]=pB;
                sizes[pB]+=sizes[pA];
            }
        }
    }
}

路径压缩优化:

对find的优化，当查询的次数远远大于数据量时， find() 的操作就已经变成了一个O(1)级别的查询时间

1
2
3
4
5
6
7
8
9
10
11
public int find(int i) {
      int h = 0;
      while (i != parent[i]) {
          help[h++] = i;	//辅助数组，将路径上的所有结点全部直接挂到root下
          i = parent[i];
      }
      for (h--; h >= 0; h--) {
          parent[help[h]] = i;
      }
      return i;
  }

947. Most Stones Removed with Same Row or Column

并查集中的parents可以不用Array而用HashMap

注意：

  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
34
35
36
37
38
39
40
41
42
public class LeetCode947 {
    public int removeStones(int[][] stones) {
        UnionFind u=new UnionFind();
        for (int[] stone : stones) {
            u.union(stone[0],~stone[1]);//& | ^ ~
        }
        return stones.length-u.total;
    }

    class UnionFind{

        Map<Integer,Integer> parents;
        int total;

        UnionFind(){
            parents=new HashMap<>();
            total=0;
        }

        int find(int i){
            if(!parents.containsKey(i)){
                parents.put(i,i);
                total++;
                return i;
            }else if(parents.get(i)!=i){
                return find(parents.get(i));
            }else{
                return i;
            }
        }

        void union(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return;
            }
            parents.put(rootA,rootB);	//合并横坐标、纵坐标的帮派
            total--;
        }
    }
}

721. Accounts Merge

1
2
3
4
1、张伟    zw2@qq.com  zw1@163.com    zw3@sina.com 
2、张伟    zw1@163.com
3、李娜    lina@qq.com
4、张伟    zhangwei@qq.com

1和2张伟是同一个人，因为有相同的邮箱，4是第二个张伟

之前做并查集有遇到一个“代表节点”的概念，也就是祖宗节点，下文的代表邮箱同理，就是把同一个人的邮箱都挂在这个人暴露出的第一个邮箱下面，像葡萄一样。

一、首先创建map存储每一个【邮箱】和【代表邮箱】之间的映射关系，它的代表邮箱先是它本身。再创建一个名为name的map存储【代表邮箱】和【账号名称】之间的映射关系，这个name的map集合最后一步要用！！！

1
2
3
邮箱     zw2@qq.com    zw1@163.com    zw3@sina.com    lina@qq.com    zhangwei@qq.com
代表邮箱 zw2@qq.com    zw1@163.com    zw3@sina.com     lina@qq.com    zhangwei@qq.com
账号姓名   张伟           张伟           张伟           李娜           张伟

二、合并同一个人的不同邮箱，就是把它的第2、3、4…….个邮箱串在代表邮箱下，像葡萄一样

1
2
邮箱 (key)       zw2@qq.com    zw1@163.com    zw3@sina.com     lina@qq.com    zhangwei@qq.com
代表邮箱(value)  zw2@qq.com     zw2@qq.com    zw2@qq.com       lina@qq.com    zhangwei@qq.com

三、创建一个map,key是代表邮箱，value是List类型，也就是代表邮箱底下挂着的同一个人的其他邮箱

1
2
3
4
做法：遍历（二）中的key，找它的代表邮箱作为key,并把它存在代表对象映射的list数组中。
例如（二）中前三个邮箱的代表邮箱都为zw@qq.com，就把它作为key,并把三个邮箱存入它对应的list中
key             zw2@qq.com                            lina@qq.com      zhangwei@qq.com
value  [ zw2@qq.com   zw1@163.com  zw3@sina.com]      [ lina@qq.com ]   [zhangwei@qq.com]

四、给同一个人的不同邮箱排序，通过Collections.sort()实现，例如get到zw2@qq.com的邮箱列表排序后213就成了123

1
2
key             zw2@qq.com                            lina@qq.com      zhangwei@qq.com
value  [ zw1@qq.com   zw2@163.com  zw3@sina.com]      [ lina@qq.com ]   [zhangwei@qq.com]

五、把代表邮箱换成对应的账号名称就OK啦，还记得第一步中创建的名为name的map集合吗，遍历（四）中的key依次获得对应的账号名字，放到数组的第一位即可。

1
2
3
4
5
6
7
List<List<String>> res = new ArrayList();  //新建结果集
       for(String root : temp.keySet()) {    //遍历（四）中的key得到代表邮箱
           List<String> layer = temp.get(root);     //通过代表邮箱获得同一人的邮箱列表 
           Collections.sort(layer);  //同一个人的不同邮箱排序
           layer.add(names.get(root)，0);  //把名字加入邮箱列表的第一位置
           res.add(layer); //把这个人的信息存入结果集
       }
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
public class LeetCode721 {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        //email union
        //email,account map 用于返回结果时对应account和email集
        //email,index map   用于合并同一个account的所有email
        Map<String,String> email_account=new HashMap<>();
        Map<String,Integer> email_index=new HashMap<>();

        int emailCount=0;
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account=accounts.get(i);
            String name=account.get(0);
            for(int j=1; j<account.size(); j++){
                String email=account.get(j);
                if(!email_account.containsKey(email)){//注意：每个email只记录第一次
                    email_account.put(email,name);
                    email_index.put(email,emailCount++);
                }
            }
        }

        UnionFind u=new UnionFind(emailCount);

        //合并同一用户的email
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account=accounts.get(i);
            String head=account.get(1);
            int a=email_index.get(head);
            for(int j=2; j<account.size(); j++){
                String next=account.get(j);
                int b=email_index.get(next);
                u.union(a,b);
            }
        }

        Map<Integer,List<String>> map=new HashMap<>();
        for (String email : email_index.keySet()) {
            int i=u.find(email_index.get(email));   //每个email属于哪个帮派
            if(!map.containsKey(i)){
                map.put(i,new ArrayList<>());
            }
            map.get(i).add(email);
        }

        List<List<String>> res=new ArrayList<>();
        for (List<String> value : map.values()) {
            String name=email_account.get(value.get(0));
            Collections.sort(value);
            List<String> list=new ArrayList<>();
            list.add(name);
            list.addAll(value);
            res.add(list);
        }
        return res;
    }

    class UnionFind{

        int[] parents;
        int[] sizes;
        int total;

        UnionFind(int n){
            parents=new int[n];
            sizes=new int[n];
            for (int i = 0; i < n; i++) {
                parents[i]=i;
                sizes[i]=1;
            }
            total=n;
        }

        int find(int i){
            while(parents[i]!=i){
                i=parents[i];
            }
            return i;
        }

        void union(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return;
            }
            if(sizes[rootA]<sizes[rootB]){
                parents[rootA]=rootB;
                sizes[rootA]+=sizes[rootB];
            }else{
                parents[rootB]=rootA;
                sizes[rootB]+=sizes[rootA];
            }
            total--;
        }
    }
}

827. Making A Large Island

DFS思路较好理解

法一：UnionFind

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
64
65
66
class Solution {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int[] p;
    int[] cnt; // 额外维护某个连通块的面积
    int ans = 1;

    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        p = new int[n * m];
        cnt = new int[n * m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    int idx = i * m + j;
                    p[idx] = idx;
                    cnt[idx] = 1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    if (i + 1 < n && grid[i + 1][j] == 1) union(i * m + j, (i + 1) * m + j);
                    if (j + 1 < m && grid[i][j + 1] == 1) union(i * m + j, i * m + j + 1);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    int temp = 1; // 当前这个位置变成1, 则面积至少为1
                    Set<Integer> set = new HashSet<>(); // 用于去重
                    for (int k = 0; k < 4; k++) {
                        int ni = i + dx[k];
                        int nj = j + dy[k];
                        if (ni < 0 || ni >= n || nj < 0 || nj >= m || grid[ni][nj] == 0) continue;
                        int idx = ni * m + nj;
                        if (set.contains(find(idx))) continue; // 该岛已经计算过, 不重复计算
                        temp += cnt[find(idx)];
                        set.add(find(idx));
                    }
                    ans = Math.max(ans, temp);
                }
            }
        }
        return ans;
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            p[px] = py;
            cnt[py] += cnt[px];
            ans = Math.max(cnt[py], ans); // 先在合并过程中, 让ans等于最大的岛的面积
        }
    }

    private int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
}

法二：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
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
class Solution {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int[] area; // 岛屿面积, 下标是岛屿编号
    int idx = 2; // 岛屿编号, 从2开始, 因为0是水域, 1是陆地
    int ans = 0;
    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        area = new int[n * m + 2]; // 对于[1] 这样的输入, 由于岛的编号从2开始, 需要多开2个大小
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    // 计算这个岛的面积
                    area[idx] = dfs(grid, i, j);
                    // 最大岛屿面积
                    ans = Math.max(ans, area[idx]);
                    // 岛的编号+1
                    idx++;
                }
            }
        }

        // 对所有的水域, 计算可能形成的最大人工岛面积
        Set<Integer> set = new HashSet<>(); // 用于去重, 声明在外面, 避免频繁创建对象
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    set.clear();
                    int t = 1;
                    for (int k = 0; k < 4; k++) {
                        int ni = i + dx[k];
                        int nj = j + dy[k];
                        if (ni < 0 || ni >= n || nj < 0 || nj >= m || grid[ni][nj] == 0) continue;
                        if (set.contains(grid[ni][nj])) continue; // 用set做去重
                        t += area[grid[ni][nj]];
                        set.add(grid[ni][nj]); // 已经出现过, 记得添加到set
                    }
                    ans = Math.max(ans, t);
                }
            }
        }

        return ans;
    }

    private int dfs(int[][] grid, int i, int j) {
        int n = grid.length, m = grid[0].length;
        grid[i][j] = idx; // 将这块陆地编号变为岛屿编号
        int res = 1; // 面积
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue; // 边界
            if (grid[ni][nj] == 0 || grid[ni][nj] > 1) continue; // 水域或者其他
            res += dfs(grid, ni, nj);
        }
        return res;
    }
}

130. Surrounded Regions

法一：岛屿DFS

先用 for 循环遍历棋盘的四边，用 DFS 算法把那些与边界相连的 O 换成一个特殊字符，比如 #；然后再遍历整个棋盘，把剩下的 O 换成 X，把 # 恢复成 O。这样就能完成题目的要求，时间复杂度 O(MN)。

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
public class LeetCode130 {
    int row;
    int col;
    char[][] board;
    public void solve(char[][] board) {
        row=board.length;
        col=board[0].length;
        this.board=board;

        for (int i = 0; i < row; i++) {
            flood(i,0);
            flood(i,col-1);
        }
        for (int j = 0; j < col; j++) {
            flood(0,j);
            flood(row-1,j);
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j]=='O'){
                    dfs(i,j);
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j]=='#'){
                    board[i][j]='O';
                }
            }
        }
    }

    void flood(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!='O'){
            return;
        }
        board[i][j]='#';
        flood(i+1,j);
        flood(i-1,j);
        flood(i,j+1);
        flood(i,j-1);
    }

    void dfs(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!='O'){
            return;
        }
        board[i][j]='X';
        dfs(i+1,j);
        dfs(i-1,j);
        dfs(i,j+1);
        dfs(i,j-1);
    }
}

法二：UnionFind

“杀鸡也可用牛刀”

二维坐标 (x,y) 可以转换成 x * n + y 这个数（m 是棋盘的行数，n 是棋盘的列数），敲黑板，这是将二维坐标映射到一维的常用技巧。

可以把那些不需要被替换的 O 看成一个拥有独门绝技的门派，它们有一个共同「祖师爷」叫 dummy，这些 O 和 dummy 互相连通，而那些需要被替换的 O 与 dummy 不连通。

323. Number of Connected Components in an Undirected Graph

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
public class LeetCode323 {
    public int countComponents(int n, int[][] edges) {
        UnionFind u=new UnionFind(n);
        for (int[] edge : edges) {
            u.union(edge[0],edge[1]);
        }
        return u.total;
    }

    class UnionFind{

        int[] parents;
        int[] sizes;	//平衡性优化
        int total;
        int[] help;		//路径压缩，只关心帮派老大是谁，老大以下众生平等
        UnionFind(int n){
            parents=new int[n];
            sizes=new int[n];
            help=new int[n];
            for (int i = 0; i < n; i++) {
                parents[i]=i;
                sizes[i]=1;
            }
            total=n;
        }

        int find(int i){
            int h=0;
            while(parents[i]!=i){
                help[h++]=i;
                i=parents[i];
            }
            for(h--; h>=0; h--){
                parents[help[h]]=i;
            }
            return i;
        }

        void union(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return;
            }
            total--;
            if(sizes[rootA]>sizes[rootB]){
                parents[rootB]=rootA;
                sizes[rootA]+=sizes[rootB];
            }else{
                parents[rootA]=rootB;
                sizes[rootB]+=sizes[rootA];
            }
        }
    }
}

990. Satisfiability of Equality Equations

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
public class LeetCode990 {
    public boolean equationsPossible(String[] equations) {
        UnionFind u=new UnionFind(26);
        //先处理等号，再判断不等号是否成立
        for (String equation : equations) {
            if(equation.charAt(1)=='='){
                char a=equation.charAt(0);
                char b=equation.charAt(3);
                u.union(a-'a',b-'a');
            }
        }

        for (String equation : equations) {
            if(equation.charAt(1)=='!'){
                char a=equation.charAt(0);
                char b=equation.charAt(3);
                if(u.connected(a-'a',b-'a')){
                    return false;
                }
            }
        }
        return true;
    }

    class UnionFind{

        int[] parents;
        int total;

        UnionFind(int n){
            total=n;
            parents=new int[n];
            for (int i = 0; i < n; i++) {
                parents[i]=i;
            }
        }

        int find(int i){
            while(parents[i]!=i){
                i=parents[i];
            }
            return i;
        }

        void union(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return;
            }
            total--;
            parents[rootA]=rootB;
        }

        boolean connected(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            return rootA==rootB;
        }
    }
}

684. Redundant Connection

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
public int[] findRedundantConnection(int[][] edges) {
    int n=edges.length;
    UnionFind u=new UnionFind(n);
    for (int[] edge : edges) {
        int a=edge[0];
        int b=edge[1];
        if(u.find(a)==u.find(b)){
            return edge;
        }
        u.union(a,b);
    }
    return null;
}

class UnionFind{
    int[] parents;
    int[] sizes;
    int[] helper;

    UnionFind(int n){
        parents=new int[n+1];
        sizes=new int[n+1];
        helper=new int[n+1];
        for (int i = 1; i <= n; i++) {
            parents[i]=i;
            sizes[i]=1;
        }

    }

    int find(int i){
        int count=0;
        while(i!=parents[i]){
            helper[count++]=i;
            i=parents[i];
        }
        for (int j = 0; j < count; j++) {
            parents[helper[j]]=i;
        }
        return i;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        int sizeA=sizes[rootA];
        int sizeB=sizes[rootB];
        if(sizeA>sizeB){
            parents[rootB]=rootA;
            sizes[rootA]+=sizeB;
        }else{
            parents[rootA]=rootB;
            sizes[rootB]+=sizeA;
        }
    }
}

685. Redundant Connection II

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public int[] findRedundantDirectedConnection(int[][] edges) {
    //no 2-in-degree node: has cycle, same as undirected
    //has a 2-in-degree node: skip those edges one by one, and see
    //if can construct a tree
    int n=edges.length;
    int[] ins=new int[n+1];
    int skip=-1;
    for (int[] edge : edges) {
        int to=edge[1];
        ins[to]++;
        if(ins[to]==2){
            skip=to;
        }
    }
    if(skip==-1){
        return helper(edges,-1);
    }else{
        for (int i = n-1; i >= 0; i--) {
            int[] edge=edges[i];
            int to=edge[1];
            if(to==skip){
                int[] res=helper(edges,i);
                if(res==null){
                    return edge;
                }
            }
        }
    }
    return null;
}

int[] helper(int[][] edges, int skip){
    int n=edges.length;
    UnionFind u=new UnionFind(n);
    for (int i = 0; i < edges.length; i++) {
        if(i==skip){
            continue;
        }
        int from=edges[i][0];
        int to=edges[i][1];
        if(u.find(from)==u.find(to)){
            return edges[i];
        }
        u.union(from,to);
    }
    return null;
}

class UnionFind{
    int[] parents;
    int[] sizes;
    int[] helper;

    UnionFind(int n){
        parents=new int[n+1];
        sizes=new int[n+1];
        helper=new int[n+1];
        for (int i = 1; i <= n; i++) {
            parents[i]=i;
            sizes[i]=1;
        }
    }

    int find(int i){
        int count=0;
        while(i!=parents[i]){
            helper[count++]=i;
            i=parents[i];
        }
        for (int j = 0; j < count; j++) {
            parents[helper[j]]=i;
        }
        return i;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        if(sizes[rootA]>=sizes[rootB]){
            sizes[rootA]+=sizes[rootB];
            parents[rootB]=rootA;
        }else{
            sizes[rootB]+=sizes[rootA];
            parents[rootA]=rootB;
        }
    }
}

721. Accounts Merge

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
64
65
66
67
//map<email,index>
//unionFind
public List<List<String>> accountsMerge(List<List<String>> accounts) {
    int n=accounts.size();
    UnionFind u=new UnionFind(n);
    Map<String,Integer> emailToIndex=new HashMap<>();
    for (int i = 0; i < n; i++) {
        List<String> account=accounts.get(i);
        String name=account.get(0);
        for (int j = 1; j < account.size(); j++) {
            String email=account.get(j);
            if(emailToIndex.containsKey(email)){
                u.union(emailToIndex.get(email),i);
            }else{
                emailToIndex.put(email,i);
            }
        }
    }
    Map<Integer,String> indexToName=new HashMap<>();
    Map<Integer, Set<String>> indexToEmails=new HashMap<>();
    for (int i = 0; i < n; i++) {
        int index=u.find(i);
        indexToEmails.putIfAbsent(index,new HashSet<>());
        List<String> account=accounts.get(i);
        String name=account.get(0);
        indexToName.put(index,name);
        for (int j = 1; j < account.size(); j++) {
            indexToEmails.get(index).add(account.get(i));
        }
    }
    List<List<String>> res=new ArrayList<>();
    for (Integer index : indexToEmails.keySet()) {
        String name=indexToName.get(index);
        LinkedList<String> list=new LinkedList<>(indexToEmails.get(index));
        Collections.sort(list);
        list.addFirst(name);
        res.add(list);
    }
    return res;
}

class UnionFind{
    Map<Integer,Integer> map;

    UnionFind(int n){
        map=new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i,i);
        }
    }

    int find(int i){
        while(i!=map.get(i)){
            i=map.get(i);
        }
        return i;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        map.put(rootA,rootB);
    }
}

305. Number of Islands II

dynamic islands => UnionFind

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
64
65
66
67
68
69
70
71
public List<Integer> numIslands2(int row, int col, int[][] positions) {
    int[] dx=new int[]{0,0,1,-1};
    int[] dy=new int[]{1,-1,0,0};
    UnionFind u=new UnionFind(row*col);
    List<Integer> res=new ArrayList<>();
    int count=0;
    for (int[] position : positions) {
        int i=position[0];
        int j=position[1];
        int idx=i*col+j;
        if(u.parent[idx]!=-1){
            res.add(count);
            continue;
        }
        u.parent[idx]=idx;
        u.size[idx]=1;
        count++;
        int x,y;
        for (int k = 0; k < 4; k++) {
            x=i+dx[k];
            y=j+dy[k];
            if(x>=0 && x<row && y>=0 && y<col && u.parent[x*col+y]!=-1){
                if(u.find(idx)!=u.find(x*col+y)){
                    u.union(idx,x*col+y);
                    count--;
                }
            }
        }
        res.add(count);
    }
    return res;
}

class UnionFind{
    int[] parent;
    int[] size;
    int[] helper;
    //[1,1] => 1*col + 1
    UnionFind(int n){
        parent=new int[n];
        size=new int[n];
        helper=new int[n];
        for (int i = 0; i < n; i++) {
            parent[i]=-1;
        }
    }

    int find(int a){
        int idx=0;
        while(parent[a]!=a){
            helper[idx++]=a;
            a=parent[a];
        }
        for (int i = 0; i < idx; i++) {
            parent[helper[i]]=a;
        }
        return a;
    }

    void union(int a, int b){
        int parentA=find(a);
        int parentB=find(b);
        if(size[parentA]>=size[parentB]){
            parent[parentB]=parentA;
            size[parentA]+=size[parentB];
        }else{
            parent[parentA]=parentB;
            size[parentB]+=size[parentA];
        }
    }
}

1168. Optimize Water Distribution in a Village

杀鸡焉用牛刀？路径优化后反而更慢

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
64
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    UnionFind u=new UnionFind(n);
    for (int i = 0; i < n; i++) {
        pq.offer(new int[]{0,i+1,wells[i]});
    }
    for (int[] pipe : pipes) {
        pq.offer(pipe);
    }
    int res=0;
    while(!pq.isEmpty()){
        int[] edge=pq.poll();
        int a=edge[0];
        int b=edge[1];
        if(u.find(a)!=u.find(b)){
            u.union(a,b);
            res+=edge[2];
        }
    }
    return res;
}

class UnionFind{
    int[] parent;
    int[] size;
    int[] helper;

    UnionFind(int n){
        parent=new int[n+1];//0, [1,n]
        size=new int[n+1];
        helper=new int[n+1];
        for (int i = 0; i <= n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }

    int find(int a){
        int idx=0;
        while(a!=parent[a]){
            helper[idx++]=a;
            a=parent[a];
        }
        for(int i=0; i<idx; i++){
            parent[helper[i]]=a;
        }
        return a;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        if(size[rootA]>=size[rootB]){
            parent[rootB]=rootA;
            size[rootA]+=size[rootB];
        }else{
            parent[rootA]=rootB;
            size[rootB]+=size[rootA];
        }
    }
}
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
class Solution {
    int[] uf;
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        uf = new int[n + 1];
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            uf[i + 1] = i + 1;
            edges.add(new int[] {0, i + 1, wells[i]});
        }
        for (int[] p : pipes) {
            edges.add(p);
        }
        Collections.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

        int res = 0;
        for (int[] e : edges) {
            int x = find(e[0]), y = find(e[1]);
            if (x != y) {
                res += e[2];
                uf[x] = y;
                
            }
        }
        return res;
    }

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

1135. Connecting Cities With Minimum Cost

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
public int minimumCost(int n, int[][] connections) {
    UnionFind u=new UnionFind(n);
    int res=0;
    Arrays.sort(connections,(a,b)->(a[2]-b[2]));
    for (int[] connection : connections) {
        int a=connection[0];
        int b=connection[1];
        if(u.find(a)!=u.find(b)){
            u.union(a,b);
            res+=connection[2];
        }
    }
    return u.count==1 ? res : -1;
}

class UnionFind{
    int[] parent;
    int[] size;
    int[] helper;
    int count;

    UnionFind(int n){
        parent=new int[n+1];
        size=new int[n+1];
        helper=new int[n+1];
        count=n;
        for (int i = 1; i <= n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }

    int find(int a){
        int idx=0;
        while(a!=parent[a]){
            helper[idx++]=a;
            a=parent[a];
        }
        for(int i=0; i<idx; i++){
            parent[helper[i]]=a;
        }
        return a;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        count--;
        if(size[rootA]>=size[rootB]){
            parent[rootB]=rootA;
            size[rootA]+=size[rootB];
        }else{
            parent[rootA]=rootB;
            size[rootB]+=size[rootA];
        }
    }
}

1319. Number of Operations to Make Network Connected

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
public class LeetCode1319 {
    public int makeConnected(int n, int[][] connections) {
        UnionFind u=new UnionFind(n);
        int free=0;
        for (int[] connection : connections) {
            int a=connection[0];
            int b=connection[1];
            if(!u.union(a,b)){
                free++;
            }
        }
        return u.count-1<=free ? u.count-1 : -1;
    }

    class UnionFind{
        int[] parent;
        int[] size;
        int[] helper;
        int count;

        UnionFind(int n){
            parent=new int[n];
            size=new int[n];
            helper=new int[n];
            count=n;
            for (int i = 0; i < n; i++) {
                parent[i]=i;
                size[i]=1;
            }
        }

        int find(int a){
            int idx=0;
            while(a!=parent[a]){
                helper[idx++]=a;
                a=parent[a];
            }
            for (int i = 0; i < idx; i++) {
                parent[helper[i]]=a;
            }
            return a;
        }

        boolean union(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return false;
            }
            if(size[rootA]>=size[rootB]){
                parent[rootB]=rootA;
                size[rootA]+=size[rootB];
            }else{
                parent[rootA]=rootB;
                size[rootB]+=size[rootA];
            }
            count--;
            return true;
        }
    }
}

2316. Count Unreachable Pairs of Nodes in an Undirected Graph

注意complexity:

  • 1 <= n <= 10^5

  • 不可最终O(n^2)遍历！

  • 而是逐步更新res

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
public long countPairs(int n, int[][] edges) {
    UnionFind u=new UnionFind(n);
    for (int[] edge : edges) {
        u.union(edge[0],edge[1]);
    }
    return u.res;
}

class UnionFind{
    int[] parent;
    int[] size;
    int[] helper;
    long res;
    UnionFind(int n){
        parent=new int[n];
        size=new int[n];
        helper=new int[n];
        res=(long)n*(n-1)/2;
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }

    int find(int a){
        int idx=0;
        while(a!=parent[a]){
            helper[idx++]=a;
            a=parent[a];
        }
        for (int i = 0; i < idx; i++) {
            parent[helper[i]]=a;
        }
        return a;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        res-=(long)size[rootA]*size[rootB];
        if(size[rootA]>=size[rootB]){
            parent[rootB]=rootA;
            size[rootA]+=size[rootB];
        }else{
            parent[rootA]=rootB;
            size[rootB]+=size[rootA];
        }
    }
}

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public int maxNumEdgesToRemove(int n, int[][] edges) {
    UnionFind u=new UnionFind(n);
    Arrays.sort(edges,(a,b)->(b[0]-a[0]));
    int res=0;
    for (int[] edge : edges) {
        int type=edge[0];
        int a=edge[1];
        int b=edge[2];
        int pa0=u.find(a,0);
        int pb0=u.find(b,0);
        int pa1=u.find(a,1);
        int pb1=u.find(b,1);
        if(type==3){
            if(pa0==pb0 && pa1==pb1){
                res++;
                continue;
            }
            if(pa0!=pb0){
                u.union(pa0,pb0,0);
            }
            if(pa1!=pb1){
                u.union(pa1,pb1,1);
            }
        }else if(type==2){
            if(pa1==pb1){
                res++;
                continue;
            }
            u.union(pa1,pb1,1);
        }else{
            if(pa0==pb0){
                res++;
                continue;
            }
            u.union(pa0,pb0,0);
        }
    }
    return u.totalA==1 && u.totalB==1 ? res : -1;
}

class UnionFind{
    int[][] parent;
    int[][] size;
    int[] helper;
    int totalA;
    int totalB;
    UnionFind(int n){
        parent=new int[n+1][2];
        size=new int[n+1][2];
        helper=new int[n];
        totalA=n;
        totalB=n;
        for (int i = 1; i <= n; i++) {
            parent[i][0]=i;
            parent[i][1]=i;
            size[i][0]=1;
            size[i][1]=1;
        }
    }

    int find(int i, int p){
        //alice: p=0;
        //bob: p=1;
        int idx=0;
        while(i!=parent[i][p]){
            helper[idx++]=i;
            i=parent[i][p];
        }
        for(int j=0; j<idx; j++){
            parent[helper[j]][p]=i;
        }
        return i;
    }

    void union(int a, int b, int p){
        //alice: p=0;
        //bob: p=1;
        if(size[a][p]>=size[b][p]){
            size[a][p]+=size[b][p];
            parent[b][p]=a;
        }else{
            size[b][p]+=size[a][p];
            parent[a][p]=b;
        }
        if(p==0){
            totalA--;
        }else{
            totalB--;
        }
    }
}

2421. Number of Good Paths

Google tag题

思路：

  1. TreeMap从小到大遍历每个val对应的node

  2. 针对每个val，探究这个val中的node能构成的good path数

    1. 该val的node的每一个帮派数为size

    2. 每一个帮派中都可以两两连接，或空连，即C size+1 2

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public int numberOfGoodPaths(int[] vals, int[][] edges) {
    int n=vals.length;
    UnionFind u=new UnionFind(n);
    Map<Integer, List<Integer>> graph=new HashMap<>();
    TreeMap<Integer,List<Integer>> valToNodes=new TreeMap<>();
    for (int i = 0; i < vals.length; i++) {
        int val=vals[i];
        valToNodes.putIfAbsent(val,new ArrayList<>());
        valToNodes.get(val).add(i);
    }
    for (int[] edge : edges) {
        int a=edge[0];
        int b=edge[1];
        graph.putIfAbsent(a,new ArrayList<>());
        graph.putIfAbsent(b,new ArrayList<>());
        graph.get(a).add(b);
        graph.get(b).add(a);
    }
    int res=0;
    for (Integer val : valToNodes.keySet()) {
        for (Integer cur : valToNodes.get(val)) {
            if(!graph.containsKey(cur)){
                continue;
            }
            for (Integer next : graph.get(cur)) {
                if(vals[next]>vals[cur]){
                    continue;
                }
                u.union(next,cur);
            }
        }
        Map<Integer,Integer> map=new HashMap<>();
        for (Integer cur : valToNodes.get(val)) {
            int root=u.find(cur);
            map.put(root,map.getOrDefault(root,0)+1);
        }
        for (Integer key : map.keySet()) {
            int size=map.get(key);
            //Cn+12
            res+=size*(size+1)/2;
        }
    }
    return res;
}

class UnionFind{
    int[] parent;
    int[] size;
    
    UnionFind(int n){
        parent=new int[n];
        size=new int[n];
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    
    int find(int i){
        while(i!=parent[i]){
            i=parent[i];
        }
        return i;
    }
    
    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        if(size[rootA]>=size[rootB]){
            size[rootA]+=size[rootB];
            parent[rootB]=rootA;
        }else{
            size[rootB]+=size[rootA];
            parent[rootA]=rootB;
        }
    }
}

399. Evaluate Division

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
64
65
66
67
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
  HashSet<String> sHashSet = new HashSet<>();
  for (List<String> List : equations)
    for (String s : List)
      sHashSet.add(s);// 初始化
  UnionFind uf = new UnionFind(sHashSet);
  for (int i = 0; i < values.length; i++) {
    List<String> list = equations.get(i);
    uf.union(list.get(0), list.get(1), values[i]);// 合并
  }
  double[] ans = new double[queries.size()];
  for (int i = 0; i < queries.size(); i++) {
    List<String> list = queries.get(i);
    String s1 = list.get(0);
    String s2 = list.get(1);
    if (uf.find(s1) == null || uf.find(s2) == null)
      ans[i] = -1;
    else if (uf.find(s1).equals(uf.find(s2))) {
      ans[i] = uf.valueMap.get(s1) / uf.valueMap.get(s2);
    } else
      ans[i] = -1;
  }
  return ans;
}

class UnionFind {
  private Map<String, String> parent; // 记录每个节点的父节点
  HashMap<String, Double> valueMap = new HashMap<>();// 记录每个string对应的值

  public UnionFind(HashSet<String> StringSet) {
    parent = new HashMap<>();
    for (String s : StringSet) { // 初始化父节点为自身
      parent.put(s, s);
      valueMap.put(s, 1.0);// 初始赋权均为0
    }
  }

  public String find(String x) {
    if (!parent.containsKey(x)) {
      return null;
    }
    String root = x;
    double base = 1;
    while (!root.equals(parent.get(root))) {// 先从x找到根节点，并更新base为到根节点的权重
      root = parent.get(root);
      base *= valueMap.get(root);
    }
    while (!x.equals(root)) {// 更新从x到根节点路径上节点的权重
      String fatherString = parent.get(x);
      valueMap.put(x, valueMap.get(x) * base);
      base /= valueMap.get(fatherString);
      parent.put(x, root);// 压缩路径
      x = fatherString;
    }
    return root;
  }

  public void union(String x, String y, Double value) {
    String rootX = find(x);
    String rootY = find(y);
    if (rootX.equals(rootY)) {
      return;
    }
    parent.put(rootX, rootY);
    valueMap.put(rootX, value * valueMap.get(y) / valueMap.get(x));
  }
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//a,b,6 ->(a,b), a:6
//a,c,2 ->(b,c), b:2*1/6
//a,b,2 => 2*12
//b,c,3 => 3*4
//c,d,4 => 4*1

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Set<String> set=new HashSet<>();
    for (List<String> equation : equations) {
        for (String s : equation) {
            set.add(s);
        }
    }
    UnionFind u=new UnionFind(set);
    int n=values.length;
    for (int i = 0; i < n; i++) {
        List<String> equation=equations.get(i);
        u.union(equation.get(0),equation.get(1),values[i]);
    }
    int len=queries.size();
    double[] res=new double[len];
    for (int i = 0; i < len; i++) {
        List<String> query=queries.get(i);
        String x=query.get(0);
        String y=query.get(1);
        if(u.find(x)==null || u.find(y)==null ||
        !u.find(x).equals(u.find(y))){
            res[i]=-1.0;
        }else{
            res[i]=u.weight.get(x)/u.weight.get(y);
        }
    }
    return res;
}

private class UnionFind{
    Map<String,String> parent;
    Map<String,Double> weight;

    UnionFind(Set<String> set){
        parent=new HashMap<>();
        weight=new HashMap<>();
        for (String s : set) {
            parent.put(s,s);
            weight.put(s,1.0);
        }
    }

    String find(String x){
        if(!parent.containsKey(x)){
            return null;
        }
        String root=x;
        double base=1.0;
        while(!root.equals(parent.get(root))){
            root=parent.get(root);
            base*=weight.get(root);
        }
        while(!root.equals(parent.get(x))){
            parent.put(x,root);
            String next=parent.get(x);
            weight.put(x,weight.get(x)*base);
            base/=weight.get(next);
            x=next;
        }
        return root;
    }

    void union(String x, String y, double value){
        String rootX=find(x);
        String rootY=find(y);
        if(rootX.equals(rootY)){
            return;
        }
        parent.put(rootX,rootY);
        //	x / y = value
        //	x / rootX = weight[x]
        //  y / rootY = weight[y]
        // rootX / rootY = (x/weight[x]) / (y/weight[y])
        // = (x/y) * (weight[y]/weight[x])
      weight.put(rootX,value*weight.get(y)/weight.get(x));
    }
}

2638. Count the Number of K-Free Subsets

思路：

  1. k-free set, 不同的set互不影响，可以随便组合
  2. 同一set内构成Fibonacci sequence
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
64
65
66
67
68
69
70
71
72
73
74
public long countTheNumOfKFreeSubsets(int[] nums, int k) {
    int n=nums.length;
    UnionFind u=new UnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if(Math.abs(nums[i]-nums[j])==k){
                u.union(i,j);
            }
        }
    }
    long res=1;
    for (int i = 0; i < n; i++) {
        if(u.find(i)==i){
            res*=cal(u.size[i]);
        }
    }
    return res;
}

private long cal(int n){
    //0: 1
    //1: 2
    //2: 3
    //3: 5
    if(n==1){
        return 2;
    }
    long a=1;
    long b=2;
    long c=0;
    for(int i=2; i<=n; i++){
        c=a+b;
        a=b;
        b=c;
    }
    return c;
}


class UnionFind{
    int[] parent;
    int[] size;

    UnionFind(int n){
        parent=new int[n];
        size=new int[n];
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }

    int find(int i){
        while(parent[i]!=i){
            i=parent[i];
        }
        return i;
    }

    void union(int a, int b){
        int rootA=find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return;
        }
        if(size[rootA]>=size[rootB]){
            size[rootA]+=size[rootB];
            parent[rootB]=rootA;
        }else{
            size[rootB]+=size[rootA];
            parent[rootA]=rootB;
        }
    }
}