dilshodp's blog

By dilshodp, 8 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.me/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.

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

| Write comment?
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I didn't downvote, but I understand why they did.

    1. What is size of SCC?
    2. What is "MAXIMUM SCC"?
    3. So what is your question? Is it even related to those question in 1/2?

    Your question is not trivial. it's simply impossible to understand.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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