Hi everyone. I have a problem with computing the size (number of the nodes) of the largest SCC of a given graph: http://mirror.codeforces.com/predownloaded/97/d6/97d6203e45199e310ddef420c28c567917a89061.jpg. Problem statement is: Given a directed graph. Compute the size (number of the nodes) of its largest SCC. I want to use Kosaraju's algo (calling DFS on the given graph and its inverted version). What happens if I first go to node root->a->b and mark node "b" as visited, then go root->c->...? Since "b" is already marked visited, in this second path "b" will not be processed, right? Then how I count the number of the nodes of root->c->...->b->root?
UPDATE Solved. It turned out, that I misunderstood the term SCC.
I don't understand those, who are putting minus. May be for you this is very trivial. But I don't think, that this is VERY trivial to be considered as a "spam"? So, please share your answer or point if I've written not enough info/correct statement. May be I omitted smth in the Kosaraju's algo and that's why can't solve this problem
I didn't downvote, but I understand why they did.
Your question is not trivial. it's simply impossible to understand.
One simple method is (if I am not wrong) using DFS...
For every node v, run DFS on both G and [lets call it, ummm] Ginverted to see which nodes are reachable from v, then nodes that are reached in both G and Ginverted are in the same SCC as v because they have a path from v to them, and from them to v... You can easily calculate the size of current SCC by counting nodes that are visited in both dfs runs.
By Ginverted, I mean a graph with same vertex-set as G, and edge set
... or just reverse the direction of the edges of G :D