給你 $n$ 個點及 $m$ 條邊的圖,並且點的編號為 $1$ 到 $n$
當滿足以下條件,稱圖為和諧的圖:
對於任意 $(l, m, r)$ 其中 $l < m < r$,若點 $l$ 到點 $r$ 之間存在一條路徑,則點 $l$ 到點 $m$ 也必須存在一條路徑
換句話說,若點 $l$ 可通過邊走到點 $r$,那麼點 $l$ 同時要能走到點 $l+1, l+2, l+3, \cdots r-1$
請問最少要加多少條邊才能使圖變為和諧的圖?
一開始給定數 $n, m$ 表示點的數量以及邊的數量 ($3 \le n \le 2\cdot 10^ 5$ 及 $1 \le m \le 2\cdot 10^ 5$)
接著有 $m$ 列,每列有兩個數 $u, v$ 表示點 $u$ 與點 $v$ 之間有邊 ($1 \le u, v \le n, u \not= v$)
輸出最少要加的邊數量,使圖變為和諧的圖。
Codeforces 1253D Harmonious Graph
No. | Testdata Range | Score |
---|---|---|
1 | 0~19 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 |