684. Redundant Connection | Cycle in an Undirected Graph | DSU | Kruskal's Idea

[@ARYANMITTAL]

DSU - th-cam.com/video/Aosw8SRp7z4/w-d-xo.html
My Uber Interview Experience - th-cam.com/video/VGYJIX5yl74/w-d-xo.html
My Coinbase Interview Experience - th-cam.com/video/IjOC18b_dCw/w-d-xo.html
My American Express Inteview Experience - th-cam.com/video/c3UhYefhnqk/w-d-xo.html
My JP Morgan & Chase Interview Experience - th-cam.com/video/-jacTpY57no/w-d-xo.html
..... more coming soon (along with LLD course on Second Channel)

[@sarankumaar6009]

thanks for the video :)

[@sanket3236]

There are multiple answers to the same graph like in the same example you can remove (1, 4) edge or (2, 3) or (3, 4) or (1, 2) to remove cycle but for the answer we need to remove the edge which appear at the last that's why answer is (1, 4).
in case of dfs this wont work as we are just detecting cycle and remove the edge which causes cycle, in the same graph start dfs with 2 -> 2,1,5,4,3,2 so here 2 is again visited to (2, 3) would be answer but it is not correct.
In case of dsu it will give correct answer as we are going in order

[@krishnaagrawal5335]

SYSTEM DESIGN WHEN?????

[@praveenukkoji]

DSU dsu(N);
for (auto edge : edges) {
// If union returns false, we know the nodes are already connected
// and hence we can return this edge.
if (!dsu.doUnion(edge[0] - 1, edge[1] - 1)) {
return edge;
}
}
// Why above code works ?
// according to question this should be the implementation right
vector lastCycleEdge;
for (const auto& edge : edges) {
if (!dsu.doUnion(edge[0]-1, edge[1]-1)) {
lastCycleEdge = edge; // Store the cycle-forming edge
}
}
return lastCycleEdge;