(Codeforces) 659E. New Reform

http://codeforces.com/contest/659/problem/E

我覺得這題出的還不錯

我的想法可能不是唯一解，但是可以參考參考。

題目大意是說：給你n座城市m條邊，你要把這m條邊給定方向。我們定義一個城市是separate如果沒有任何一條邊指向他，例如：a-->b, b-->c，a就是separate的城市。

我的想法是：

先用kruscal求出Minimum Spanning Tree(最小生成樹)，並且在求出MST的過程中，維護有哪些邊已經用過了(在MST裡面的邊)。

到這個階段，我們已經知道答案最多是 所有子MST數量 + 沒有被邊連到的點。

說明一下為什麼目前的答案是 所有子MST數量 + 沒有被邊連到的點 ： 因為MST有n個點，n-1個邊，我隨便找一個點當樹根(root)，把樹根當成separate的城市，之後的邊，都指向自己的兒子，這樣就OK了。

之後，對於沒有在MST裡面的邊，我先看說這個邊是在哪個子MST裡面(如果在兩個不同的子MST裡面，那個邊也一定會是MST的邊)，如果這個子MST沒有被加邊過，我就把這個邊加到這個MST裡面，這樣答案就可以-1了(想想看，把剛剛當樹根的點設為新邊的其中一個點，那還有新的一條邊可以回到自己)。

這樣就Accepted了。

Code : http://codepad.org/XgOK7d5b