1->2
1->3
so
par[1]=3
par[2]=3
par[3]=3
but there is no path from 2 to 3
so they should be in different components
Connected components
@PoojaSingh22,
What you are talking about is directed graph, and connected components is not definable there. Instead, there we consider Strongly connected components, which cannot be found using DSU.
Anyways, you cannot detect cycle in directed graphs using DSU, you would need modifies dfs to do that. DSU cycle detection only works for undirected graphs.
okk thanks…it means the example m taking cannot be solved using kruskals
@PoojaSingh22,
Yep, either modified dfs or Kosaraju’s algorithm can be used, depending on the problem.