-
Notifications
You must be signed in to change notification settings - Fork 7
/
Main.java
41 lines (35 loc) · 1 KB
/
Main.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
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
}
int[] parents;
int[] rank;
public int[] findRedundantConnection(int[][] edges) {
parents = new int[edges.length];
rank = new int[edges.length];
for (int i = 0; i < parents.length; i++)
parents[i] = i;
for (int[] edge : edges) {
if (!Union(edge[0] - 1, edge[1] - 1))
return edge;
}
return null;
}
private int Find(int x) {
if (parents[x] != x)
parents[x] = Find(parents[x]);
return parents[x];
}
private boolean Union(int x, int y) {
int rootX = Find(x), rootY = Find(y);
if (rootX == rootY) return false;
if (rank[rootX] >= rank[rootY]) {
parents[rootY] = rootX;
if (rank[rootX] == rank[rootY])
rank[rootX]++;
} else
parents[rootX] = rootY;
return true;
}
}