系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

【英雄哥六月集训】第 22天: 有序集合

【英雄哥六月集训】第 23天: 字典树

【英雄哥六月集训】第 24天: 线段树

【英雄哥六月集训】第 25天: 树状数组

【英雄哥六月集训】第 26天: 并查集

---

并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

一、 二维网格图中探测环

1559. 二维网格图中探测环

class Solution {
    class UnionFind{
        int[] parent;
        int[] size;
        int n;
        int setCount;

        public UnionFind(int n){
            parent = new int[n];
            for(int i = 0;i<n;i++){
                parent[i]=i;
            }
            size = new int[n];
            Arrays.fill(size,1);
            this.n=n;
            setCount=n;
        }

        public int findset(int x){
            return parent[x] == x?x:(parent[x]=findset(parent[x]));
        }

        public void unite(int x,int y){
            //确保y的 size 小
            if(size[x]<size[y]){
                int temp = x;
                x = y;
                y=temp;
            }
            parent[y]=x;
            size[x]+=size[y];
            --setCount;
        }

        public boolean findAndUnite(int x,int y){
            int parentX = findset(x);
            int parentY = findset(y);
            if(parentX !=parentY){
                unite(parentX,parentY);
                return true;
            }
            return false;
        }
    }
    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        UnionFind uf = new UnionFind(m*n);
        for(int i=0;i<m;++i){
            for(int j = 0;j<n;++j){
                if(i>0 && grid[i][j]==grid[i-1][j]){
                    if(!uf.findAndUnite(i*n+j,(i-1)*n+j)){
                        return true;
                    }
                }
                if(j>0 && grid[i][j]==grid[i][j-1]){
                    if(!uf.findAndUnite(i*n+j,i*n+j-1)){
                        return true;
                    }
                }
            }
        }
        return false;

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

---

二、 检查网格中是否存在有效路径

1391. 检查网格中是否存在有效路径

class Solution {
    class UnionFind{
        int[] f;

        public void initset(){
            f = new int[250010];
            for(int i = 0;i<250010;i++){
                f[i]=i;
            }
        }

        public int findset(int x){
            return f[x] == x?x:(f[x]=findset(f[x]));
        }

        public int unionset(int x,int y){
            int fx=findset(x);
            int fy=findset(y);
            if(fx!=fy){
                f[fx]=fy;
                return 1;
            }
            return 0;
        }
    }
    int[][] dir=new int[][] {
        {-1,0},{0,1},{1,0},{0,-1}
    };

    int[][][] data=new int [][][]{
        {{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}},
        {{-1,-1,-1},{1,3,5},{-1,-1,-1},{1,4,6}},
        {{2,3,4},{-1,-1,-1},{2,5,6},{-1,-1,-1}},
        {{-1,-1,-1},{-1,-1,-1},{2,5,6},{1,4,6}},
        {{-1,-1,-1},{1,3,5},{2,5,6},{-1,-1,-1}},
        {{2,3,4},{-1,-1,-1},{-1,-1,-1},{1,4,6}},
        {{2,3,4},{1,3,5},{-1,-1,-1},{-1,-1,-1}}
    };
    public boolean hasValidPath(int[][] grid) {
        UnionFind uf=new UnionFind();
        int i,j,k;
        int m = grid.length;
        int n= grid[0].length;
        uf.initset();
        for(i=0;i<m;i++){
            for(j=0;j<n;++j){
                for(k=0;k<4;++k){
                    int ti=i+dir[k][0];
                    int tj=j+dir[k][1];
                    if(ti<0||tj<0||ti==m||tj==n){
                        continue;
                    }
                    int a = i*n+j;
                    int b = ti*n+tj;
                    int ag = grid[i][j];
                    int bg = grid[ti][tj];

                    if(data[ag][k][0]==bg|| data[ag][k][1]==bg || data[ag][k][2]==bg){
                        uf.unionset(a,b);
                    }
                }
            }
        }
        return uf.findset(0)==uf.findset(m*n-1);

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

三、 交换字符串中的元素

1202. 交换字符串中的元素

class Solution {
    int[] f;

    public void initset(int n){
        f = new int[n];
        for(int i = 0;i<n;i++){
            f[i]=i;
        }
    }

    public int findset(int x){
        if(x!=f[x]){
            f[x]=findset(f[x]);
        }
        return f[x];
    }
 

    

    
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        initset(n);
        for(int j=0; j<pairs.size();j++){
            List<Integer> pa = pairs.get(j);
            int pre = pa.get(0);
            int aft = pa.get(1);

            int preP = findset(pre);
            int aftP = findset(aft);
            if(preP == aftP){
                continue;
            }
            f[preP] = aftP;
        }
        Map<Integer,PriorityQueue<Character>> map = new HashMap<>();
        for(int k = 0;k<n;k++){
            PriorityQueue<Character> queue = map.getOrDefault(findset(k),new PriorityQueue<>());
            queue.offer(s.charAt(k));
            map.put(f[k],queue);
        }

        StringBuilder sb=new StringBuilder();
        for(int r=0;r<n;r++){
            PriorityQueue<Character> tq = map.get(findset(r));
            sb.append(tq.poll());
        }
        return sb.toString();
    
    }
}
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

总结