2050 . 尋找關節點 EXTREME

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 8qbfbv4
baluteshih

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

12.9% (4/31)

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