Tìm khớp xung yếu
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đơn đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Một đỉnh được gọi là khớp (articulation point) nếu khi xóa đỉnh đó cùng các cạnh liên thuộc với nó, số thành phần liên thông của đồ thị tăng lên. Hãy tìm tất cả các đỉnh khớp của đồ thị.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, 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$ ($1 \le u, v \le N$, $u \ne v$, không có cạnh song song).
Dữ liệu ra
- Dòng đầu tiên in ra số lượng đỉnh khớp $K$.
- Nếu $K > 0$, dòng thứ hai in ra $K$ đỉnh khớp theo thứ tự tăng dần, cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 5 5 1 2 2 3 3 1 3 4 4 5 |
2 3 4 |
| 4 4 1 2 2 3 3 4 4 1 |
0 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion