dilshodp's blog

By dilshodp, 7 years ago, In English

Hi everyone. I have a problem with computing the size (number of the nodes) of the largest SCC of a given graph: http://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.

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it