2050 . 尋找關節點 EXTREME

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 8qbfbv4
baluteshih

User's AC Ratio

65.2% (15/23)

Submission's AC Ratio

13.8% (30/218)

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

No. Testdata Range Score
1 0~31 21
2 0~65 28
3 0~99 51

Testdata and Limits

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