Strongly Connected Components

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

12 years ago, # |

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':

→ Reply

Gassa

12 years ago, # ^ |

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 V², but for the general case, I doubt your estimate.

→ Reply

12 years ago, # ^ |

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

12 years ago, # |

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

http://www.lightoj.com/volume_showproblem.php?problem=1417

12 years ago, # ^ |

yes, I run the both dfs starting from vertex 1, but, I'm didn't got why the matrix MB mark the edges as the opposite of MA(which are the real edges) It's doesn't make much sense to me, here's is my code, which surprisingly got accepted: http://pastebin.com/z8FKjkDM

if you know other problems which involve SCC, send me, I want to try if this strategy works in other problems.

→ Reply

faiyaz26

12 years ago, # ^ |

← Rev. 3 →

you can try this: http://www.lightoj.com/volume_showproblem.php?problem=1034

→ Reply

12 years ago, # ^ |

With the help of MB (by the way it is useless, since MB is just transposed MA ) you may check if there are paths TO starting vertex. If there is a path in MB from A to B, then in real graph there will be path from B to A.

This algo will not help you to find SCC, only to check if graph in whole is strongly connected.

You can try solving http://acm.timus.ru/problem.aspx?space=1&num=1198&locale=en . I can't remember any other link to problem, related with SCC.

→ Reply

12 years ago, # ^ |

It only works if I want to find if the whole graph is an SCC ? if I need to count the number of different SCC what's the best algorithm I should use ?

→ Reply

12 years ago, # ^ |

I don't know any way to count SCC other than to find them all with the help of algorithms you mentioned in your post.

→ Reply

12 years ago, # ^ |

I've been reading about Kosajaru's algorithm and implemented this solution, which seems a lot with my old one, it passed the tests with a good time.. is it a truly implementation of Kosajaru's ? http://pastebin.com/jKbv5Beb

→ Reply

12 years ago, # ^ |

Yes it is :)

→ Reply

12 years ago, # ^ |

Thank you, I'm proud of myself ;)

→ Reply

9 years ago, # |

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

9 years ago, # ^ |

+14

What's a SCC in an undirected graph?

→ Reply

http://mirror.codeforces.com/gym/100676

9 years ago, # ^ |

In such contest, the solution of the last problem pointed out that we need to get the SCC of the graph. Any idea?

→ Reply

pwild

9 years ago, # ^ |

Note that what the problem statement refers to as "strongly connected" is not what one usually means when using that term.

Instead, what is described there is more along the lines of 2-edge-connected components. On that topic, the following wiki article should be helpful: https://en.wikipedia.org/wiki/Bridge_(graph_theory)

→ Reply

9 years ago, # ^ |

We can transform a directed graph using SCC to a DAG.

Can we do the same if we find the biconnected components?

→ Reply

9 years ago, # ^ |

SCC and BC are NOT in the same graph.

→ Reply

9 years ago, # ^ |

of course they are not in the same graph. What i meant is, if i found some way the biconnected components of an undirected graph, can i create a DAG out of it if i contract all the BC?

→ Reply

9 years ago, # ^ |

DAG is NOT defined in an undirected graph.

→ Reply

9 years ago, # ^ |

can we transform it into an undirected tree then?

→ Reply

9 years ago, # ^ |

→ Reply

9 years ago, # ^ |

Why not? If we compress all biconnected components into a single vertex we get a tree (or a forest if the initial graph isn't connected).

→ Reply

9 years ago, # ^ |

One node can be part of many biconnected components. How do you define the tree for the initial graph : 1 — 2 — 3 ?

→ Reply

9 years ago, # ^ |

The tree should be the same as the graph since it's a tree in this case (1-2-3), I think.

→ Reply

9 years ago, # ^ |

I don't think it matters. You can apply the BC algorithm for trees too.

For 1-2-3-4 you have the resulting tree (1,2)-(3,4) but for 1-2-3 you have(1,2) and (2,3) and they are not linked. The definition of a tree has to change in order to make it work.

→ Reply

9 years ago, # ^ |

"Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph." — https://en.wikipedia.org/wiki/Biconnected_component

So what I meant was just to make all bridges the edges of our so-called block-cut tree (I count A-B as a bridge if there is no other path from A to B) so in this case a tree with N nodes always has N biconnected components, one node in each component :)

→ Reply