1457 . 圖形加密系統
TopCoder
Tags
Description
資訊科學中的有向圖(Directed-Graph)是一種很有趣的資料結構。
今天你研發出了一種加密有向圖的方式：
加密的圖形中有 m 個頂點，分別來自原始圖的每一條邊。
當原始圖的PA→PB以及PB→PC存在時，則在加密的圖形中劃上一條PAB→PBC。
現在你得到了一個加密之後的圖形，但是你擔心加密的過程中是否有問題，所以你決定判斷一下他是否是一個經過正確加密過的圖形。
Input Format
本題有多組測試資料：
第一行有一個數字 T ，代表有 T 組圖形需要判斷
每組測試資料的：
第一行有一個數字 n ，代表這組圖形中有 n 個點。( 0 < n <= 500)
第二行有一個數字 m ，代表這組圖形中有 m 條邊。( 0 <= m <= 100,000)
接下來有 m 行，每行有兩個數字ai,bi，代表從ai到bi有一條有向邊
Output Format
對於每筆測試資料輸出是否是經過正確加密過的圖形。
Sample Input 1
4
2
1
0 1
5
0
4
3
0 1
2 1
2 3
3
9
0 1
0 2
1 2
1 0
2 0
2 1
0 0
1 1
2 2
2
1
0 1
5
0
4
3
0 1
2 1
2 3
3
9
0 1
0 2
1 2
1 0
2 0
2 1
0 0
1 1
2 2
Sample Output 1
Case #1: Yes
Case #2: Yes
Case #3: No
Case #4: Yes
Case #2: Yes
Case #3: No
Case #4: Yes
Hints
※2008/10/29 題目敘述補注 by hallogameboy。感謝 akira。
Problem Source
原TIOJ1457 / 建中校內培訓第三次模擬考試。
Problem Setter：hallogameboy、peter50216
(Adapt From：Uva 11175)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |