b570. 為什麼你們都喜歡撞來撞去的?
Tags :
Accepted rate : 133人/160人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-09-22 04:58

Content

板燒國是一個大國,板燒國裡有許多城市,每個城市都單獨在一座島上,城市與城市之間有橋連接。甲哥是一名恐怖分子,他很討厭板燒國,他覺得這國家的人都在撞來撞去真是太不爽了。所以他決定要拆散這個國家,於是他想把城市與城市之間的橋給炸掉。他想知道炸掉幾座橋之後,板燒國被分成了幾塊,互相連通的城市屬於同一塊。

Input

第一行有兩個正整數n, m (n<=10000, m<=1000000),代表有n個城市以及m座橋,城市編號為1~n。
接下來有m行,第1行是編號1的橋,第2行是編號2的橋,以此類推。每行有兩個正整數a, b,代表這座橋連接a, b兩座城市。
接下來有一個正整數q(q<=m),代表要毀掉q座橋。
接下來q行每行有一正整數表示要毀掉編號為幾的橋。
(已經炸掉的橋不會復原)

Output

每炸掉一座橋就輸出一次目前板燒國被分成了幾塊。

Sample Input #1
3 3
1 2
2 3
1 3
3
1
2
3
Sample Output #1
1
2
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 5.0s , <1K
公開 測資點#1 (20%): 5.0s , <1M
公開 測資點#2 (20%): 5.0s , <1M
公開 測資點#3 (20%): 5.0s , <50M
公開 測資點#4 (20%): 5.0s , <50M
Hint :
Tags:
出處:
104學年度板橋高中校內資訊學科能力競賽(四) [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
18746 rsj00008 (二信008) b570
解法思路
1240 2019-08-03 18:10