Can we detect cycles in directed graph using Union-Find data structure?
No.
Let me give you an example:
- Q1. Take an undirected graph:
Is there a cycle in above undirected graph? Yes. And we can find the cycle using Union-Find algo.
- Q2. Now look at the similar directed graph:
Is there a cycle in above directed graph? No! BUT if you use Union-Find algo to detect cycle in above directed graph, it will say YES! Since union-find algo looks at the above diagram as below:
OR
Is there a cycle in above diagram? Yes! But the original(Q2) question was tampered and this is not what was asked. So Union-find algo will give wrong results for directed graphs.
No, we cannot use union-find to detect cycles in a directed graph. This is because a directed graph cannot be represented using the disjoint-set(the data structure on which union-find is performed).
When we say 'a union b' we cannot make out the direction of edge
- is a going to b? (or)
- is b going to a?
But, incase of unordered graphs, each connected component is equivalent to a set. So union-find can be used to detect a cycle. Whenever you try to perform union on two vertices belonging to the same connected component, we can say that cycle exists.