最近做了好多题都或多或少和并查集带点关系,稍微记录一下

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
package 并查集模板;  

public class Main {
static int[] pre;
static int[] sum;
public static void main(String[] args) {
// TODO Auto-generated method stub

}

static int find(int x) {
int r = x;
while (pre[r] != r)
r = pre[r];
int i = x, j;
while (i != r) {
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}

static void union(int x, int y){
int fx = find(x), fy = find(y);
if (fx != fy){
pre[fx] = fy;
sum[fy]+=sum[fx];
}

}
}