Các Thành Phố Cần Thiết

Điểm: 1,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

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $n$ thành phố và $m$ con đường hai chiều. Đảm bảo rằng từ bất kỳ thành phố nào cũng có thể đến bất kỳ thành phố nào khác.

Một thành phố gọi là cần thiết nếu xóa thành phố đó (cùng tất cả các con đường nối với nó) sẽ làm cho đồ thị không còn liên thông. Hãy tìm tất cả các thành phố cần thiết.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ — con đường nối thành phố $a$ và $b$ .

Dữ liệu ra

Dòng 1: số nguyên $k$ — số thành phố cần thiết.
Dòng 2: $k$ số nguyên phân cách bởi dấu cách — các thành phố cần thiết (theo thứ tự bất kỳ).

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \cdot 10^{5}$
$1 \leq a, b \leq n$
Mỗi con đường nối hai thành phố phân biệt

Ví dụ

Input	Output	Giải thích
5 5 1 2 1 4 2 4 3 5 4 5	2 4 5	Xóa thành phố 4 ngắt kết nối {1,2} khỏi {3,5}. Xóa thành phố 5 ngắt kết nối {1,2,4} khỏi {3}.
2 1 1 2	0	Không có thành phố nào cần thiết (chỉ có một con đường).

Bình luận

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