Cải cách đường bộ

Điểm: 5,00 (OI)

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

Python 3 5.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

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một đồ thị vô hướng có $n$ đỉnh và $m$ cạnh. Không có cạnh nối một đỉnh với chính nó, và giữa mỗi cặp đỉnh có không quá một cạnh. Đồ thị không bắt buộc phải liên thông.

Bạn cần định hướng (gán hướng) cho mỗi cạnh, biến nó thành một cạnh có hướng (chỉ đi từ một đỉnh sang đỉnh kia).

Gọi một đỉnh là cô lập nếu không có cạnh có hướng nào đi vào nó (đỉnh đó có thể có cạnh đi ra, nhưng không có cạnh đi vào).

Hãy tìm cách định hướng các cạnh sao cho số đỉnh cô lập là nhỏ nhất có thể, và in ra số lượng đỉnh cô lập đó.

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên dương $n$ và $m$ — số đỉnh và số cạnh.
$m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $x_{i}$ , $y_{i}$ ( $x_{i} \neq y_{i}$ ), mô tả một cạnh vô hướng nối đỉnh $x_{i}$ và $y_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất — số đỉnh cô lập nhỏ nhất sau khi định hướng tối ưu.

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 10^{5}$
$1 \leq x_{i}, y_{i} \leq n$ , $x_{i} \neq y_{i}$
Giữa mỗi cặp đỉnh có không quá một cạnh.

Ví dụ

Input	Output	Giải thích
4 3 2 1 1 3 4 3	1	Đồ thị là một cây 4 đỉnh. Cây không có chu trình nên bắt buộc phải có ít nhất một đỉnh cô lập (gốc của định hướng).
5 5 2 1 1 3 2 3 2 5 4 3	0	Đồ thị liên thông có chu trình (5 đỉnh, 5 cạnh). Có thể định hướng sao cho mỗi đỉnh đều có ít nhất một cạnh vào.
6 5 1 2 2 3 4 5 4 6 5 6	1	Hai thành phần liên thông: ${1, 2, 3}$ là cây (cần 1 cô lập), ${4, 5, 6}$ là tam giác có chu trình (cần 0 cô lập). Tổng: 1.

Bình luận

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