Блог пользователя zscoder

CPSPC 2010 Sailor
Автор zscoder, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is there an English problem statement?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить