2050 . 尋找關節點 EXTREME
TopCoder
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 1
6 7
1 2
1 3
2 3
3 4
4 5
5 6
4 6
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
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 |