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
Imagine a graph with
X
vertices1..X
in one component and 2 verticesX+1, X+2
in another component with edgesX+1 -> X+2
andX+2 -> X+1
. Add an edge fromX
toX+1
. Your DFS will find every non cyclic path from1
toX+1
, and will backtrack each time it goes fromX+2
back toX+1
.If the
1..X
component has an edge between each pair of vertices, the number of paths in the first component is greater thanX!
.The reason for getting WA and not TLE is that you're numbering the latter component with an increased
g
value every time you find it, and at some pointg > N
, but your union-findparent
array is initialized only up toN
. I think all the cases you get a correct answer on have a relatively small number of edges.