PKU2375-Cow Ski Area

題目：http://poj.org/problem?id=2375
有個棋盤W*L(500*500)，每格有它的高度(地形棋盤)
滑雪的規則是這樣的：
1.每次走上下左右一格
2.只能從地形高的格子走到低的格子或一樣高的格子
現在Farmer Ron (不是FJ!!!)想要為他的滑雪場造一些纜車，
「一架纜車」可以為地形圖上任意兩格提供無條件的雙向連結
問最少要架幾架纜車，才能使得所有格子之間都可以互相到達？


程式碼：http://codepad.org/G0xsLDuJ
來源是USACO 2004 December Gold
金組題目果然不少是IOI經典改編
整題的模型和http://poj.org/problem?id=1236 (IOI1996)十分神似

以圖論的角度來分析，
把棋盤上共250000格全部拆成一個一個點、相鄰如果可以滑雪到達就建一條單向邊
並且找出所有「強連通分量」然後「縮點」變成「有向無環圖(DAG)」
有了DAG很容易看得出來，
我們想造纜車的位置可以從「山頂(沒邊連到它)」和「山腳(沒邊連出去)」中選擇
經過幾番精妙的思考得出一個結論：答案就是 max(入度為0的點數, 出度為0的點數)
另外有一個特例：當DAG只有一個點
這時不用造纜車也可以通行、答案是0
總結以上兩點本題得解

不不不，我才懶得寫Tarjan、這題有不必縮點的做法
平心而論，高點走到低點是單向、高度一樣是雙向的
因此得到一個簡單的結論：相鄰連通並且高度一樣的區域、是一個強連通分量
所以一開始把整張棋盤掃過、給高度一樣的相鄰區定一個點編號
然後再掃地二遍、考慮各點之間的連通關係，
甚至不必維護鄰接表，只要判斷「有無入邊」「有無出邊」即可

(我後來拿網路上Tarjan的code自己生測資對照
發現兩種算出來的強連通分量各數是一樣無誤的)