-
Notifications
You must be signed in to change notification settings - Fork 5
/
UnionFind6.java
70 lines (59 loc) · 1.47 KB
/
UnionFind6.java
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
package com.github.junyu.solution.data_structure.union_find;
/**
* 并查集,路径压缩,find时通过递归将遍历过的元素都指向根节点,使树的深度
* 更低
*
* @author ShaoJunyu
*/
public class UnionFind6 {
private int parents[];
private int ranks[];
private int count;
public UnionFind6(int size) {
count = size;
parents = new int[size];
ranks = new int[size];
for (int i = 0; i < size; i++) {
parents[i] = i;
ranks[i] = 1;
}
}
/**
* 查看p元素对应的集合
*
* @param p
* @return
*/
public int find(int p) {
if (p < 0 || p > count)
throw new RuntimeException("IndexOutOfBoundsException");
if (p != parents[p]) {
parents[p] = find(parents[p]);
}
return parents[p];
}
/**
* 查看p和q元素是否属于一个集合
*
* @param p
* @param q
* @return
*/
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
if (ranks[rootP] > ranks[rootQ]) {
parents[rootQ] = rootP;
} else if (ranks[rootP] < ranks[rootQ]) {
parents[rootP] = rootQ;
} else {
parents[rootP] = rootQ;
ranks[rootQ]++;
}
}
}