Các Con Đường 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 con đường gọi là cần thiết nếu xóa nó sẽ làm cho đồ thị không còn liên thông (tức là tồn tại một cặp thành phố không thể đến nhau). Hãy tìm tất cả các con đường 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ố con đường cần thiết.
$k$ dòng tiếp theo: mỗi dòng gồm hai số nguyên mô tả một con đường 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$
Không có hai con đường nối cùng một cặp thành phố
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 3 5 4 5	Xóa cạnh 3–5 hoặc 4–5 đều làm ngắt kết nối đồ thị. Các cạnh 1–2, 1–4, 2–4 tạo thành chu trình nên không cần thiết.
4 3 1 2 2 3 3 4	3 1 2 2 3 3 4	Đây là một đường thẳng — mọi cạnh đều cần thiết.

Bình luận

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