給你一個有向圖(directed graph),請問該圖的最小圈(cycle)長度為何?
輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有兩個正整數n,m(1<=n<=500;1<=m<=250,000),代表該圖的點數和邊數。
頂點的編號從1到n。
接下來有m列,每列用兩個整數i,j(1<=i,j<=n)描述一條有向邊,從編號i到編號j。
當n=m=0時代表輸入結束。你可以假設輸入的圖不會有self-cycle的出現。
對於每筆測試資料,請輸出最小圈的邊長。如果該圖沒有圈,請輸出0。
範例輸入當中,最小的cycle為(1→2→3→4→1或1→5→3→4→1)
原TIOJ1212 / TIOJ 2008例行賽03 (prob D)。經典問題練習。Problem Setter:Tmt。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 33 |
2 | 1 | 33 |
3 | 2 | 34 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 5000 | 65536 | 262144 | |
1 | 5000 | 65536 | 262144 | |
2 | 5000 | 65536 | 262144 |