forked from yennanliu/CS_basics
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTestEnv1.java
More file actions
75 lines (61 loc) · 1.72 KB
/
TestEnv1.java
File metadata and controls
75 lines (61 loc) · 1.72 KB
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
package dev;
public class TestEnv1 {
// custom UF
class UF1{
// attr
int[] degree;
int[] parents; // ???
int cnt;
// constructor
UF1(int n){
this.degree = new int[n];
this.parents = new int[n];
this.cnt = cnt;
// init values
for(int i = 0; i < n; i ++){
this.degree[i] = 0;
this.parents[i] = i;// node's parent is itself at beginning
}
}
// method
/**
* find(x): Get root parent of x with path compression
* union(x, y): Connect two nodes, return false if already connected
* connected(x, y): Check if two nodes are in same component
*/
// ok
public int find(int x){
// ???? while or if ??
// -> yes. while
while(this.parents[x] != x){
/**
* parent[x] = parent[parent[x]];
* x = parent[x];
*
*/
// correct
this.parents[x] = find(x);
}
return this.parents[x]; // ???
}
// ok
public void union(int x, int y){
if(x == y){
return;
}
int parentX = this.find(x);
int parentY = this.find(y);
// need to do `path relaxation` ??? (via `rank`)
// ???
this.parents[x] = parentY; // ???
this.cnt -= 1;
}
// ok
public boolean connected(int x, int y){
if(x == y){
return true;
}
return this.find(x) == this.find(y);
}
}
}