b201:npsc2008高中組初賽 F. 國家
zerojudge連結 http://zerojudge.tw/ShowProblem?problemid=b201
內容 ：
傳說在遙遠的古代，整個地球的大陸是一整塊，整塊大陸上有n 個城市。這些城市間有共有m 條道路相連接，不過有趣的是這些道路只能夠單向通行。有一天上帝決定把整塊大陸切成幾塊形成各自的國家。分割的策略就是把原本就可以互相聯絡的幾個城市當成一個國家（如果有一條路徑從城市i 到城市j 且有一條路徑從城市j 到城市i，則城市i 和城市j 就在同一個國家）。上帝想請你幫一個忙，他想知道每個國家的大小。也就是每個國家到底包含了幾個城市。
以下是一個簡單的例子：
如果有一條單行道從城市 i 接到城市j 用(i,j)表示如果一開始有 3 個城市，然後有3 條單行道(1, 2), (2, 1), (2, 3) 則可以分成兩個國家，分別包含了2 個城市(1, 2)和1 個城市(3)。
輸入說明 ：
輸入檔中會有多筆資料，每一組資料的第一行第一行包含了城市數量 n(1<=n<=100000)和單行道的數量m(1<=m<=2100000)，接下來m 行，每一行中都包含兩個數字i, j 代表有一條單行道從城市i 連到城市j(注意兩個城市間可能有不只兩條的單行道)。
輸出說明 ：
對於每一組資料輸出一行，內容是排序過後每個國家的大小。
範例輸入 ：
3 3
1 2
2 1
2 3
2 2
1 2
2 1
範例輸出 ：
1 2
2
提示 ：
出處 ：
2008 NPSC 高中組初賽
解題策略
強連通圖Strongly Connected Components(SCC)
根據Kosaraju's Algorithm，使用DFS走訪Graph的每個點Finish時間，最先Finish的先加入stack，由stack依Finish時間由最晚到最早取出，走訪反向的Graph，能走訪到的就是可連接起來的強連通圖。
參考資料
1. http://www3.tcgs.tc.edu.tw/npsc/index.php?topic=25.0 NPSC補完計畫