2050 . 尋找關節點 EXTREME

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 8qbfbv4
baluteshih

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

16.0% (13/81)

Tags

Description

給一張$N$點$M$邊的無向圖，保證連通、不含有自環、重邊。
請輸出滿足$a < b$且原圖移除$a, b$兩點後會不連通的點對$(a, b)$數量。

Input Format

第一行有兩個正整數$N, M(N\leq 2000, N - 1\leq M \leq \frac{N(N - 1)}{2})$，分別代表點數以及邊數。
接著$M$行每行有兩個正整數$u_i, v_i$，代表第$i$條邊連接$u_i$以及$v_i$。

子任務（測資） 額外限制 分數
1 (0~31) $N \leq 100$ 21
2 (0~65) $N \leq 800$ 28
3 (0~99) $N \leq 2000$ 51

Output Format

輸出一個整數代表有幾對$(a, b)$滿足$a < b$且移除點$a$以及點$b$後會造成圖不連通。

Sample Input

Sample Input #1
6 7
1 2
1 3
2 3
3 4
4 5
5 6
4 6

Sample Input #2
4 4
1 2
2 3
3 4
1 4

Sample Output

Sample Output #1
9

Sample Output #2
2

Hints

範例測資一：移除$(1, 3)$、$(1, 4)$、$ (2, 3)$、$ (2, 4)$、 $(3, 4)$、 $(3, 5)$、$ (3, 6)$、$ (4, 5)$、 $(4, 6)$後皆會造成圖不連通。
範例測資二：移除$(1, 3)$、$(2, 4)$後皆會造成圖不連通。

Problem Source

Problem Set by WeaK, waynetuinfor

Subtasks

For Testdata: 0 ~ 31, Score: 21
For Testdata: 0 ~ 65, Score: 28
For Testdata: 0 ~ 99, Score: 51
No. Time Limit (ms) Memory Limit (KiB)
0 2000 262144
1 2000 262144
2 2000 262144
3 2000 262144
4 2000 262144
5 2000 262144
6 2000 262144
7 2000 262144
8 2000 262144
9 2000 262144
10 2000 262144
11 2000 262144
12 2000 262144
13 2000 262144
14 2000 262144
15 2000 262144
16 2000 262144
17 2000 262144
18 2000 262144
19 2000 262144
20 2000 262144
21 2000 262144
22 2000 262144
23 2000 262144
24 2000 262144
25 2000 262144
26 2000 262144
27 2000 262144
28 2000 262144
29 2000 262144
30 2000 262144
31 2000 262144
32 2000 262144
33 2000 262144
34 2000 262144
35 2000 262144
36 2000 262144
37 2000 262144
38 2000 262144
39 2000 262144
40 2000 262144
41 2000 262144
42 2000 262144
43 2000 262144
44 2000 262144
45 2000 262144
46 2000 262144
47 2000 262144
48 2000 262144
49 2000 262144
50 2000 262144
51 2000 262144
52 2000 262144
53 2000 262144
54 2000 262144
55 2000 262144
56 2000 262144
57 2000 262144
58 2000 262144
59 2000 262144
60 2000 262144
61 2000 262144
62 2000 262144
63 2000 262144
64 2000 262144
65 2000 262144
66 2000 262144
67 2000 262144
68 2000 262144
69 2000 262144
70 2000 262144
71 2000 262144
72 2000 262144
73 2000 262144
74 2000 262144
75 2000 262144
76 2000 262144
77 2000 262144
78 2000 262144
79 2000 262144
80 2000 262144
81 2000 262144
82 2000 262144
83 2000 262144
84 2000 262144
85 2000 262144
86 2000 262144
87 2000 262144
88 2000 262144
89 2000 262144
90 2000 262144
91 2000 262144
92 2000 262144
93 2000 262144
94 2000 262144
95 2000 262144
96 2000 262144
97 2000 262144
98 2000 262144
99 2000 262144
Submit
Status
Ranklist
Back to Top