aajjbb's blog

Strongly Connected Components
By aajjbb, 14 years ago, In English

Hi, Searching for how to find if a give graph _G_is Strongly Connected (There's a path from any vertex to any other vertex) I figured out about Kosajaru's Algorithm and Tarjan's Algorithm, but looking in other solutions for problems involving SCC, I've found an interesting approach which does not fit in any of the two algorithm, but worked for me in a problem in SPOJ-BR:

Mounting the Adjacency Matrix:

It's used 2 Matrices, MA and MB:

If there's a Path from Vertex A -> B: MA[A][B] = true; mark the opposite in matrix MB: MB[B][A] = true;

Then: dfs through them, first in MA, if the number of visited vertexes are equals to the number of vertexes in the graph G, then, the graph is strongly connected, if not, dfs though matrix MB, and again, if the number of visited vertexes is the number of vertexes in the graph G, the graph is strongly connected.

Is it a well known algorithm, it works in any case to look for SCC ?

Thanks in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
14 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

What time does it take to construct MA and MB?

→ Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please, give a link of this problem and your code!

→ Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

sorry for the delay:

Build the matrices MA and MB has the same cost O(N) with N-> the number of edges in the graph G:

The problem is this one, sorry because the statement is in portuguese, but it asks for a simple '1' if the given graph is strongly connected, otherwise '0':

http://br.spoj.pl/problems/IREVIR/

→ Reply
  • »
    »
    14 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I don't quite get how exactly do you correctly initialize V × V memory in E operations, where V is the number of vertices and E is the number of edges.

    In this particular problem, E can be of order V2, but for the general case, I doubt your estimate.

    → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I read all the N edges from the input, Initially all the indices of the V*V matrix are zeroes, and while I'm reading the edges from input, I mark the indices W-V and V-W as 1 being V and W two connected vertexes.

      → Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I didn't really understand why should the algo, that you described, work. I think both conditions must be satisfied. In my opinion algo should be like this:

Select some vertex A. Run dfs from A in matrix MA and count the number of vertices. Then run dfs from A in matrix MB and also count the number of vertices. Both numbers should be equal to number of vertices in graph.

This algorithm will work, since we may build the following path from U to V: U -> A -> V. And the check of number above will guarantee that from every vertex we can reach A and from A we can reach V.

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

Does kosaraju and Tarjan algortihms works on undirected graph?

if no is the answer, how can i find the SCC in an undirected graphs?

→ Reply