傳說在遙遠的古代,整個地球的大陸是一整塊,整塊大陸上有 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
Migrated from old NTUJ.
NPSC預賽
No. | Testdata Range | Score |
---|