2050 . 尋找關節點 EXTREME

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

73.3% (22/30)

Submission's AC Ratio

15.9% (43/270)

Tags

Description

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

Input Format

第一行有兩個正整數N,M(N≤2000,N−1≤M≤N(N−1)2)，分別代表點數以及邊數。
接著M行每行有兩個正整數ui,vi，代表第i條邊連接ui以及vi。

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

Output Format

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

Sample Input 1

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

Sample Output 1

9

Sample Input 2

4 4
1 2 
2 3
3 4
1 4

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, 100 21
2 0~65, 100 28
3 0~100 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
100 2000 262144 262144 1 2 3
Submit
Back to Top