vamaddur's blog

Proof For Minimal Number of Edges Added to Make a Directed Graph Strongly Connected
By vamaddur, history, 7 years ago, In English

Link

Can someone prove the correctness of the approach described in the first answer on the thread? I understand why the first step is crucial as a starting point.

Thanks in advance!

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

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

Old Codeforces thread on the same topic.

It also reminded me an ancient TopCoder problem. It looks very similar, but extremely tricky.

→ Reply