780 . 圖論之最小圈測試

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

75.0% (3/4)

Tags

apcsc apcsc-graph

Description

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

Input Format

輸入檔的第一列有兩個正整數 $n$, $m$ ，代表該圖的點數和邊數。
頂點的編號從 $1$ 到 $n$。
接下來有 $m$ 列，每列用兩個整數 $i,j$（$1\le i,j \le n$）描述一條有向邊，從編號 $i$ 到編號 $j$。
你可以假設輸入的圖不會有自環（self-cycle）的出現。

  • $1 \le n \le 500$
  • $1 \le m \le n(n-1)$

Output Format

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

Sample Input 1

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

Sample Output 1

4

Hints

Problem Source

TIOJ 1212

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~32 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
32 1000 524288 65536 2
Submit
Back to Top