使用场景

  1. 一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
  2. int find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合，查找过程中进行扁平化
  3. boolean isSameSet(a, b)：判断a和b在不在一个集合里，即判断a和b的代表是否是同一个
  4. void union(a, b)：a所在集合所有元素 与 b所在集合所有元素 合并成一个集合，可能进行小挂大
  5. 各种操作单次调用的均摊时间复杂度为O(1)

题目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
68
69
70
71
72
73
74
75
76
package com.study.class56;
​
import java.io.*;
​
public class Code01 {
    public static int MAXN = 1000001;
    public static int[] father = new int[MAXN];
    public static int[] size = new int[MAXN];//用于小挂大
    public static int[] stack = new int[MAXN];//用于扁平化,路径压缩
    public static int n;
    //初始化时所有集合代表都是本身，大小都为1
    public static void build(){
        for(int i=0;i<= n;i++){
            father[i]=i;
            size[i]=1;
        }
    }
    public static int find(int i){
        int size = 0;
        while(i!=father[i]){
            stack[size++] = i;
            i = father[i];
        }
        //将查找路径上的所有元素都指向最终元素
        while(size > 0){
            father[stack[--size]] = i;
        }
        return i;
    }
    public static boolean isSameSet(int x,int y){
        return find(x) == find(y);
    }
    public static void union(int x,int y){
        int i =find(x);
        int j=find(y);
        if(i==j){//是同一个集合
            return;
        }else{
            if(size[i] >= size[j]){
                size[i]+=size[j];
                father[j]=i;
            }else{
                size[j]+=size[i];
                father[i]=j;
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int) in.nval;
            build();
            in.nextToken();
            int m = (int) in.nval;
            for(int i=0;i<m;i++){
                in.nextToken();
                int op  = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                in.nextToken();
                int y = (int) in.nval;
                if(op == 1){
                    out.println(isSameSet(x, y) ? "Yes" : "No");
                }else{
                    union(x, y);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}
​

题目2

题目链接：P3367 【模板】并查集 - 洛谷

  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
package com.study.class56;
​
import java.io.*;
​
public class Code02 {
    public static int MAXN = 200001;
    public static int[] father = new int[MAXN];
    public static int n;
    public static void build(){
        for(int i = 0;i <= n;i++){
            father[i]=i;
        }
    }
    public static int find(int i){
        if(i != father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }
    public static boolean isSameSet(int x,int y){
        return find(x) == find(y);
    }
    public static void union(int x,int y){
        father[find(x)]=find(y);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int) in.nval;
            in.nextToken();
            build();
            int m =  (int) in.nval;
            for(int i = 0;i < m;i++){
                in.nextToken();
                int op = (int)in.nval;
                in.nextToken();
                int x = (int)in.nval;
                in.nextToken();
                int y = (int)in.nval;
                if(op == 1){
                    union(x,y);
                }else{
                    out.println(isSameSet(x,y) ? "Y": "N");
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

题目3

题目链接：765. 情侣牵手

解题思路

  1. **初始化并查集，共 **n = row.length / 2 个情侣组；

  2. 遍历每个座位

    • 计算两人所属的情侣组：a = row[i] / 2, b = row[i+1] / 2
    • **在并查集中合并 **a 和 b

  3. 设最终连通分量数量为 ,一个分组中有n队情侣，交换次数为n-1

    1
    sets

    ，则答案为：ans=n−sets

代码

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 static int MAXN = 31;
    public static int[] father = new int[MAXN];
    public static int sets;
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        build(n/2);
        for(int i = 0;i < n;i+=2){
             union(row[i]/2,row[i+1]/2);
        }
        return n/2 - sets;
    }
    public static void build(int m){
        for(int i = 0;i < m;i++){
            father[i] = i;  
        }
        sets = m ;
    }
    public static int find(int i){
        if(i != father[i]){
            father[i] = find(father[i]);
        }
        return father[i];
    }
    public static void union(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy;
            sets--;
        }
    }
}

题目4

题目链接：839. 相似字符串组 - 力扣（LeetCode）

解题思路

  1. 初始化并查集：每个字符串自成一组（共 n 组）。
  2. **枚举所有字符串对 **(i, j)
    • 若在一个集合，跳过；
    • **否则逐位比较 **strs[i] 和 strs[j]，统计不同位置数 diff；
    • **若 **diff == 0 或 diff == 2（完全相同或相似），执行 union(i, j)。
  3. 返回最终的组数 sets。

代码

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
class Solution {
    public static int MAXN = 301;
    public static int[] father = new int[MAXN];
    public static int sets;
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        build(n);
        for(int i = 0;i < n;i++){
            for(int j = i + 1;j < n;j++){
                if(find(i) != find(j)){//不在同一个集合
                   int diff = 0;
                   for(int k = 0;k < m&& diff < 3;k++){//逐位比较
                       if(strs[i].charAt(k) != strs[j].charAt(k)){
                        diff++;
                       }
                   }
                   if(diff == 0 || diff == 2){
                    union(i,j);
                   }
                }
            }
        }
        return sets;
    }
    public static void build(int n){
         for(int i = 0;i < n;i++){
            father[i] = i;
         }
         sets = n;
    }
    public static int find(int i){
        if(i != father[i]){
            father[i] = find(father[i]);
        }
        return father[i];
    }
    public static void union(int i,int j){
        int fi = find(i);
        int fj = find(j);
        if(fi != fj){
            father[fi] = fj;
            sets--;//合并集合数减1
        }
    }
}

题目5

题目链接：200. 岛屿数量

解题思路

  1. **将每个 **'1' 视为一个独立节点。
  2. 遍历网格，若当前格子是 '1'，则检查其左邻居和上邻居是否也是 '1'。
    • 每一个节点都会遍历其左边和右边，不会遗漏
  3. 如果是，则将当前格子与邻居****合并到同一集合。
  4. 最终剩余的集合数即为岛屿数量。

代码

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 {
    public static int MAXN = 300001;
    public static int[] father = new int[MAXN];
    public static int sets;
    public static int cols;
​
    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        build(grid,n,m);
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(grid[i][j] == '1'){
                    if(j > 0 && grid[i][j-1] == '1'){
                        union(index(i,j),index(i,j-1));
                    }
                    if(i > 0 && grid[i-1][j] == '1'){
                        union(index(i,j),index(i-1,j));
                    }
                }
            }
        }
        return sets;
​
    }
​
    public static void build(char[][] grid, int n, int m) {
        sets = 0;
        cols = m;
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    index = index(i, j);
                    father[index] = index;
                    sets++;//初始化时每个'1'都是1个集合
                }
            }
        }
    }
    //将二维坐标（i,j）映射到一维坐标上
    public static int index(int i, int j) {
        return i * cols + j;
    }
​
    public static int find(int i){
        if(i != father[i]){
            father[i] = find(father[i]);
        }
        return father[i];
    }
     
    public static void union(int i,int j){
        int fi = find(i);
        int fj = find(j);
    if(fi != fj){
        father[fi] = fj;
        sets--;
    }
    }
}