This medium LC problem is about finding the edge which causes the tree to have a cycle.
To solve this, we can just use Disjoint Set data structure to build the connected components and as soon as we find any edge which causes two nodes to be on the same set then we’ve found our answer.
Time complexity: O(NLogN + E), N = number of nodes, E = number of edges Space complexity: O(N)
class Solution {
class DisjointSet {
private Map<Integer, Node> mapping = new HashMap<>();
class Node {
int data;
int rank;
Node parent;
}
public void makeSet(int data){
final Node node = new Node();
node.data = data;
node.rank = 0;
node.parent = node;
mapping.put(data, node);
}
public int find(int data){
return find(mapping.get(data)).data;
}
private Node find(Node node){
final Node parent = node.parent;
if(node.data == parent.data) return parent;
// path compression
node.parent = find(parent);
return node.parent;
}
public void union(int x, int y){
Node xSet = find(mapping.get(x));
Node ySet = find(mapping.get(y));
if(xSet.data == ySet.data) return;
// union by rank
if(xSet.rank >= ySet.rank){
xSet.rank = xSet.rank == ySet.rank ? xSet.rank + 1 : xSet.rank;
ySet.parent = xSet;
}else {
xSet.parent = ySet;
}
}
}
public int[] findRedundantConnection(int[][] edges) {
final DisjointSet ds = new DisjointSet();
final int len = edges.length;
for(int i=1; i <= len; i++){
ds.makeSet(i);
}
for(int[] edge : edges){
int x = ds.find(edge[0]);
int y = ds.find(edge[1]);
if(x == y) return edge;
ds.union(x, y);
}
return new int[0];
}
}
Runtime: 2 ms, faster than 35.62% of Java online submissions for Redundant Connection. Memory Usage: 41.1 MB, less than 27.27% of Java online submissions for Redundant Connection.