并查集

近似 O(1)的时间复杂度

并查集能解决什么问题?

  • 如何合并两个集合
  • 如何两个元素在不在同一个区间内

并查集原理?

用一棵树来存储整个集合,树根的编号就是整个集合的编号。每个节点存储它的父节点,p[x]代表它的父节点

衍生出问题

  1. 如何判断树根?if(p[x] == x)
  2. 如何求 x 的编号?while(p[x] != x) x = p[x]
  3. 如何合并两个集合,x 代表第一个集合,y 代表第二个集合?p[x] = y

如何优化?

每遍历一次,让这个节点直接指向根节点,即可将时间复杂度优化为 O(1);

模版应用

836. 合并集合

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
import java.util.*;
import java.io.*;
public class Main{
private static int p[] = new int[100010]; //声明父节点;
public static void main(String [] args) throws IOException {
Scanner in = new Scanner(new BufferedInputStream(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = in.nextInt();
for(int i = 1 ; i <= n ; i ++)p[i] = i;
int m = in.nextInt();
while(m -- != 0){
String op = in.next();
if(op.equals("M")){
int a = in.nextInt();
int b = in.nextInt();
p[find(a)] = find(b);
}else{
int a = in.nextInt();
int b = in.nextInt();
if(find(a) == find(b))log.write("Yes\n");
else log.write("No\n");
}
}
log.flush();
log.close();
}
//查找x节点的父亲
public static int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
}

837. 连通块中点的数量

同时维护当前区间内,有多少个数量

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
import java.util.*;
import java.io.*;
public class Main{
public static int p[] = new int[100010];
public static int size[] = new int[100010];

public static void main(String[] args) throws IOException
{
Scanner in = new Scanner(new BufferedInputStream(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = in.nextInt();
int m = in.nextInt();
for(int i = 1 ; i <= n ; i ++){
p[i] = i;
size[i] = 1;
}
while(m -- != 0){
String op = in.next();
if(op.equals("C")){

int a = in.nextInt();
int b = in.nextInt();
if(find(a) == find(b)) continue;
size[find(b)] += size[find(a)];
p[find(a)] = b;
}else if(op.equals("Q1")){
int a = in.nextInt();
int b = in.nextInt();
if(find(a) == find(b))log.write("Yes\n");
else log.write("No\n");
}else{
int k = in.nextInt();
log.write(size[find(k)] + "\n");
}
}
log.flush();
log.close();

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

240. 食物链

维护当前集合里面到根节点的距离

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
import java.io.*;
import java.util.*;
public class Main{
public static int[] p,d; //p存储父节点 d存储距离
public static void main(String[] args) throws IOException{
Scanner in = new Scanner(new BufferedInputStream(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = in.nextInt();
int m = in.nextInt();
p = new int[n + 1];
d = new int[n + 1];
int ans = 0 ; //表示假话的个数
for(int i = 1 ; i <= n ; i ++)p[i] = i;
while(m -- != 0){
int op = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
if(x > n || y > n){
ans += 1;
continue;
}
int px = find(x);
int py = find(y);
switch (op) {
case 1 : {
//同一个集合中,表示已确立相互关系
if (px == py) {
if ((d[x] - d[y])%3 != 0) {
ans++;
continue;
}
}
//不同集合中,现在建立相互关系
else {
d[px] = d[y] - d[x];
p[px] = py;
}
break;
}
case 2 : {
//同一个集合中,表示已确立相互关系
if (px == py) {
//推导出的关系为 (d[x]-d[y])%3 == 1 则认为x可以吃y
//写成(d[x]-d[y]-1)%3 == 0 可以避免余数是负数的问题
//也可以写成(d[x]-d[y])%3 +3 == 1
//==正确 -> != 错误
if ((d[x] - d[y] - 1) % 3 != 0) {
ans++;
continue;
}
}
//不同集合中,现在建立相互关系
else {
d[px] = d[y] - d[x] + 1;
p[px] = py;
}
break;
}
default : System.out.print("--");
}
}
log.write(ans + " ");
log.flush();
log.close();
}
public static int find(int x){
if(x != p[x]){
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
}
作者

Codecat

发布于

2021-09-10

更新于

2021-09-20

许可协议

评论