In the lecture DSU 04 - Cycle Detection & Implementation, Prateek bhaiya has considered directed edges in the graphs, i.e added edges unidirectionally.
I believe cycle detection using DSU will fail for Directed graphs.
Consider the case of a graph with 3 vertices and 3 edges :
1->2, 1->3, 2->3
parent[2] = 1, parent[3] = 1, => DSU says that cycle exists but clearly, the graph is acyclic
If indeed this is the case that the DSU cycle detection doesn’t work for Directed Graphs, what must be done to tackle the fact that the adjacency list will have edges in both directions in an Undirected Graph?
One approach can be to traverse the adjacency list and create an edge list having only unique edges and then apply DSU.
Is there any other approach which doesn’t require creating such a new edge list and strictly applies teh DSU algorithm? (not BFS/DFS).