1212 . 圖論 之 最小圈測試

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

94.9% (37/39)

Submission's AC Ratio

52.6% (50/95)

Tags

TIOJcon 2008-TIOJcon-3rd

Description

給你一個有向圖(directed graph)，請問該圖的最小圈(cycle)長度為何？

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有兩個正整數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的出現。

Output Format

對於每筆測試資料，請輸出最小圈的邊長。如果該圖沒有圈，請輸出0。

Sample Input

5 7
1 2
3 4
2 5
5 3
1 5
4 1
2 3
0 0

Sample Output

4

Hints

範例輸入當中，最小的cycle為(1→2→3→4→1或1→5→3→4→1)

Problem Source

原TIOJ1212 / TIOJ 2008例行賽03 (prob D)。經典問題練習。Problem Setter：Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536
1 5000 65536 65536
2 5000 65536 65536
Submit
Status
Ranklist
Back to Top