Đồ thị điều hòa

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một đồ thị vô hướng đơn $G$ gồm $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ $1$ đến $n$ .

Đồ thị được gọi là điều hòa nếu thỏa mãn tính chất sau:

Với mọi bộ ba số nguyên $(l, m, r)$ mà $1 \leq l < m < r \leq n$ , nếu trong $G$ tồn tại đường đi từ đỉnh $l$ đến đỉnh $r$ thì cũng phải tồn tại đường đi từ đỉnh $l$ đến đỉnh $m$ .

Nói cách khác, nếu từ đỉnh $l$ ta có thể đến đỉnh $r$ với $l < r$ , thì ta cũng phải đến được mọi đỉnh có chỉ số nằm giữa, tức $l + 1, l + 2, \dots, r - 1$ .

Hãy tính số cạnh ít nhất cần thêm vào $G$ để đồ thị trở nên điều hòa.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_{i}, v_{i}$ ( $u_{i} \neq v_{i}$ ) — mô tả một cạnh nối đỉnh $u_{i}$ với $v_{i}$ .

Đồ thị là đơn (không có cạnh khuyên và không có hai cạnh nối cùng một cặp đỉnh).

Dữ liệu ra

In ra một số nguyên duy nhất — số cạnh tối thiểu cần thêm để đồ thị trở nên điều hòa.

Ràng buộc

$3 \leq n \leq 200 000$
$1 \leq m \leq 200 000$
$1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$

Ví dụ

Input	Output	Giải thích
200000 3 7 9 9 8 4 5	0	Đồ thị đã điều hòa: thành phần ${7, 8, 9}$ và ${4, 5}$ đều có các đỉnh liên tiếp.
14 8 1 2 2 7 3 4 6 3 5 7 3 8 6 8 11 12	1	Từ đỉnh $1$ có thể đến đỉnh $7$ nhưng không đến được $6$ . Thêm cạnh $(2, 4)$ là đủ để đồ thị điều hòa.
3 1 1 3	1	Từ $1$ đến $3$ được nhưng không đến được $2$ , phải thêm $1$ cạnh.

Bình luận

Không có bình luận tại thời điểm này.