prrateekk's blog

Problem with strongly connected components
By prrateekk, history, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Imagine a graph with X vertices 1..X in one component and 2 vertices X+1, X+2 in another component with edges X+1 -> X+2 and X+2 -> X+1. Add an edge from X to X+1. Your DFS will find every non cyclic path from 1 to X+1, and will backtrack each time it goes from X+2 back to X+1.

If the 1..X component has an edge between each pair of vertices, the number of paths in the first component is greater than X!.

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 point g > N, but your union-find parent array is initialized only up to N. I think all the cases you get a correct answer on have a relatively small number of edges.

→ Reply