HOJ100-選秀

題目：http://hoj.mooo.com/judge/index.php/problem/view/100
給一張具有n(100000)個點的有向圖、邊不超過1000000條
存在邊(u,v)代表選手u比賽的時候一定會贏選手v
(是故u,v和v,u只可能有一條存在)
如果u和v之間沒有邊存在，那麼比賽的時候有可能u贏v也可能反過來
比賽的順序是任意的，問有哪些人「有可能」奪冠？


程式碼：http://codepad.org/mbFbTGki
本來剛看到這題，就用眼睛AC它了：
為這個圖建一個「可能勝利圖」、如果u,v沒邊就補上u<->v雙向邊
然後Tarjan求強連通分量，縮點後位居DAG最高處(沒入邊)的點群就是所求點
而且這樣的點群只會有一群

DFS的時間複雜度是O(E)，而這樣做法的E會和點數平方成正比、也就是十萬的平方

才恍然大悟這題給圖的方式是很特別的(很機車的)，沒辦法硬幹

經過多番筆記證明小定理左試右試以後，整題的結論如下：

我們首先定義所求的點是「王點」(可能奪冠的選手)、其餘點都是「奴點」

(1)設v是王點，如果不存在邊v->u的話、那麼u也是王點【可能贏王的人也是王】
證明略

(2)如果奴點存在的話，設王點集Vk、奴點集Vs共S個點，那麼所有的Vk都具有S條連線連到所有Vs。即所有的Vk(i) -> Vs(j)屬於E【霸凌現象】
證明：反證法假設有任一條Vk(i') -> Vs(j')不存在，那麼根據(1)表示Vs(j')是王點、矛盾

(神來一筆地跳到性質3)

(3)凡王點的入度數必定小於奴點的入度數
證明：令n個點中有k個王點
A.k=n時，奴點不存在、命題成立
B.k<n時
B-1奴點的入度數>=k (根據性質2)
B-2王點的入度數<=k-2：由於只有王點能指向王點，理想上最多會有k-1個點指向一王、但是這麼做會發生被指向點變成沒辦法奪冠的矛盾，所以入度數至多k-2
總結得王入<=k-2<k<奴入，遞移得王入<奴入

--------------------
設計算法：
首先，根據各點的入度數由小到大穩定排序
由於性質3的關係、可以想見王點會粘在左邊，奴點會粘在右邊(如果有的話)

再由性質2可知，左側的點「共同」連向的右側點才可能是奴點

所以整個算法的策略就是首先認定王數ans是1
(K=王、.=不確定、S=奴)
整條待辦陣列會像是：K.......
再來由左到右選出每個確定是王的點u
從這點的出邊中確定有k個連續的點擠在右邊：類似像這樣(k=3)
K KKKK ...
因為沒被指向的點一定是王點所以有四個小點點突然長大了
掃過去以後K會漸漸接近答案、點點會縮小
全部的K掃過以後，就能達成性質2的條件、本題得解
KKKKKSSS

嗯…後半寫得有點亂，我盡量取名和程式碼的取名一致了