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.
What time does it take to construct MA and MB?
Please, give a link of this problem and your code!
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/
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.
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.
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.
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.
you can try this: http://www.lightoj.com/volume_showproblem.php?problem=1034
http://www.lightoj.com/volume_showproblem.php?problem=1417
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.
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 ?
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.
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
Yes it is :)
Thank you, I'm proud of myself ;)
Does kosaraju and Tarjan algortihms works on undirected graph?
if no is the answer, how can i find the SCC in an undirected graphs?
What's a SCC in an undirected graph?
http://codeforces.net/gym/100676
In such contest, the solution of the last problem pointed out that we need to get the SCC of the graph. Any idea?
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)
We can transform a directed graph using SCC to a DAG.
Can we do the same if we find the biconnected components?
SCC and BC are NOT in the same graph.
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?
DAG is NOT defined in an undirected graph.
can we transform it into an undirected tree then?
NO
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).
One node can be part of many biconnected components. How do you define the tree for the initial graph : 1 — 2 — 3 ?
The tree should be the same as the graph since it's a tree in this case (1-2-3), I think.
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.
"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 :)
I agree with this decomposition. I was talking (and I think that's that WalidMasri meant) about using the component as a vertex (as in SCC) not about the block-cut tree.