-
Notifications
You must be signed in to change notification settings - Fork 62
/
Solution.java
59 lines (47 loc) · 1.77 KB
/
Solution.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
package g1301_1400.s1319_number_of_operations_to_make_network_connected;
// #Medium #Depth_First_Search #Breadth_First_Search #Graph #Union_Find
// #Graph_Theory_I_Day_8_Standard_Traversal #2022_03_19_Time_9_ms_(67.64%)_Space_64.6_MB_(49.60%)
import java.util.Arrays;
public class Solution {
private static final int IMPOSSIBLE_TO_CONNECT = -1;
private int disconnectedComputers;
private int[] parent;
private int[] rank;
public int makeConnected(int totalNumberOfComputers, int[][] connections) {
if (connections.length < totalNumberOfComputers - 1) {
return IMPOSSIBLE_TO_CONNECT;
}
disconnectedComputers = totalNumberOfComputers;
rank = new int[totalNumberOfComputers];
parent = new int[totalNumberOfComputers];
Arrays.setAll(parent, intFromZero -> intFromZero++);
for (final int[] connection : connections) {
unionFind(connection[0], connection[1]);
}
return disconnectedComputers - 1;
}
private void unionFind(int first, int second) {
int parentFirst = findParent(first);
int parentSecond = findParent(second);
if (parentFirst != parentSecond) {
joinByRank(parentFirst, parentSecond);
disconnectedComputers--;
}
}
private int findParent(int index) {
if (parent[index] != index) {
parent[index] = findParent(parent[index]);
}
return parent[index];
}
private void joinByRank(int first, int second) {
if (rank[first] < rank[second]) {
parent[first] = second;
} else if (rank[second] < rank[first]) {
parent[second] = first;
} else {
parent[first] = second;
rank[second]++;
}
}
}