I was trying to solve this problem based on strongly connected components — Problem
Strongly connected components can be found using Tarjan's but I haven't studied it yet!
I tried to solve it using the following information —
- All the nodes involved in a cycle are strongly connected.
- Two cycles with atleast one node in common forms strongly connected component.
I marked all the nodes in a cycle with a 'type'. When I encounter a node with some other 'type' (which means it belongs to other cycle as well), I make the disjoint set union of the two cycles.
Is there something I'm missing in my approach?
Here's my code -CODE