d197: 11504 - Dominos
Tags :
Accepted rate : 98人/156人 ( 63% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-04-23 17:57

Content

骨牌很好玩。孩子們喜歡把它們立起來排成一長排,當一張骨牌倒下,它會把下一張推倒,這一張又會把下一張推倒,一直下去。不過有時候會有某一張骨牌倒下時並沒有推倒下一張,這時候就得用手把它推倒,好使其餘的骨牌繼續倒下。

給你一些骨牌的排列方式,你的任務是要算出至少要用手推倒幾張骨牌才能讓所有的骨牌全倒下。

Input

輸入的第一行有一個整數代表以下有幾組測試資料。每組測試資料的第一行有兩個不大於 100 000 的整數:第一個整數 n 代表有幾張骨牌,骨牌的編號為 1 n;第二個整數 m 代表以下有幾行測資,每行有兩個整數 x y,表示如果 x 骨牌倒下時,y 骨牌也會跟著倒下。

Output

對於每組測試資料,輸出含有一個整數的一行。該整數表示至少要用手推倒幾張骨牌才能讓所有的骨牌全倒下。

Sample Input
1
3 2
1 2
2 3
Sample Output
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <10M
Hint :

UVa 原題

上傳 UVa 時需用 scanf, printf 才不會超時。

Tags:
出處:
UVa11504 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」