Tìm Khớp Của Đồ Thị
Xem dưới dạng PDF
Gửi bài giải
Điểm:
30
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Kiểu bài tập
Mạng lưới giao thông huyết mạch vô hướng nối liền \(N\) trung tâm logistics nông sản của hợp tác xã bằng \(M\) tuyến đường hai chiều liên kết.
Một trung tâm \(u\) được xem là "điểm trung chuyển trọng yếu" (khớp - cut vertex) nếu khi trung tâm này ngừng hoạt động (do bảo trì hoặc thiên tai), mạng lưới giao thông còn lại sẽ bị chia cắt thành nhiều phần độc lập làm gián đoạn chuỗi cung ứng.
Hãy giúp An tìm tất cả các điểm trung chuyển trọng yếu và in ra theo thứ tự tăng dần.
Định dạng đầu vào
- Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
- \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả tuyến đường giữa trung tâm \(u\) và \(v\).
Định dạng đầu ra
- Dãy số hiệu các trung tâm trọng yếu theo thứ tự tăng dần cách nhau bởi dấu cách.
Ví dụ
Input:
4 4
1 2
2 3
3 1
3 4
Output:
3
Nhận xét