https://neetcode.io/problems/redundant-connection?list=neetcode150
initial
isnt this unnecessary edge just if both nodes have already been visited thats that unnecessary edge?
no cuz if u have
edges = [[1,2],[3,4],[1,3],[2,4]][1,2]: add, mark 1 & 2 visited
[3,4]: add, mark 3 & 4 visited
[1,3]: both 1 & 3 visited → your method flags it?
✅ Correct, [1,3] connects two components → not redundant yet
Actually, [1,3] is needed to keep graph connected, so marking both visited is misleading
[2,4]: both 2 & 4 visited → this is the real redundant edge
If you only check “visited”, you might incorrectly flag [1,3] as redundant.
sol
instead my initial thought of union find is the sol. If find_parent(node1) ==find_parent(node2), this means those 2 nodes have already been connected together before. So this is the unnecessary cycle
rmb union find lazily loads parents so u have to call find_parent, not just parent[node]
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] parent = new int[edges.length+1];
for(int i=0;i<edges.length+1;i++){
parent[i]=i;
}
List<int[]> ans = new ArrayList<>();
for(int[] edge:edges){
if(find_parent(parent,edge[0])==find_parent(parent,edge[1])){
ans.add(edge);
}
else{
union(parent,edge[0],edge[1]);
}
}
return ans.get(ans.size()-1);
}
public int find_parent(int[] parent, int node){
if(parent[node]!=node){
parent[node]=find_parent(parent,parent[node]);
}
return parent[node];
}
public void union(int[] parent, int node1, int node2){
int par1 = find_parent(parent,node1);
int par2 = find_parent(parent,node2);
if (par1<par2){
parent[par2]=par1;
} else{
parent[par1]=par2;
}
}
}
complexity
o(n) time and space
