zscoder's blog

CPSPC 2010 Sailor
By zscoder, history, 10 years ago, In English

I was trying to solve this problem.

I could only figure out the naive solution. (DFS from each vertex) I think I have encountered similar problems before but I couldn't solve them either. How do I solve this kind of problem?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Is there an English problem statement?

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

The problem isn't that hard.

My idea is to compress the graph into strongly connected components. Then the new graph will be DAG. Lets call a LEAF every vertex with 0 outcoming edges. The value will be equal to the minimal size of a leaf (number of vertexes in leaf). This can be simply solved just by finding the leaves.

Overall complexity: O(N+M).

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I see. I was thinking of SCC but didn't know how to proceed. I never used the trick of compressing SCCs into single vertices before.

    → Reply