Created with IntelliJ IDEA User Andrey Kudryavtsev Date 07 11 13 Time

 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
* Created with IntelliJ IDEA.
* User: Andrey Kudryavtsev
* Date: 07.11.13
* Time: 22:11
*/
public class WeightedQuickUF
{
private int[] id; // id[i] = parent of i
private int[] sz; // sz[i] = number of objects in subtree rooted at i
private int count; // number of components
/**
* Create an empty union find data structure with N isolated sets.
*
* @param N Num of sets
*/
public WeightedQuickUF(int N)
{
count = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++)
{
id[i] = i;
sz[i] = 1;
}
}
/**
* Return the number of disjoint sets.
*
* @return the number of disjoint sets
*/
public int count()
{
return count;
}
/**
* Return component identifier for component containing p
*
* @param p
* @return component identifier for component containing p
*/
public int find(int p)
{
while (p != id[p])
p = id[p];
return p;
}
/**
* Are objects p and q in the same set?
*
* @param p object1
* @param q object2
* @return Are objects p and q in the same set
*/
public boolean isConnected(int p, int q)
{
return find(p) == find(q);
}
/**
* Replace sets containing p and q with their union.
*
* @param p object1
* @param q object2
*/
public void union(int p, int q)
{
int i = find(p);
int j = find(q);
if (i == j)
return;
// make smaller root point to larger one
if (sz[i] < sz[j])
{
id[i] = j;
sz[j] += sz[i];
} else
{
id[j] = i;
sz[i] += sz[j];
}
count--;
}
}