Cho một đơn đồ thị vô hướng liên thông. Một đỉnh là trọng yếu nếu sau khi xóa đỉnh đó cùng mọi cạnh kề, có hai đỉnh còn lại không còn đường đi giữa chúng. Hãy liệt kê tất cả các đỉnh trọng yếu.
Input
Dòng đầu chứa hai số nguyên n và m.
Mỗi trong m dòng tiếp theo chứa hai đầu mút u và v của một cạnh vô hướng.
Output
Dòng đầu in số lượng đỉnh trọng yếu k.
Dòng thứ hai in k chỉ số đỉnh theo thứ tự tăng dần; dòng này để trống khi k=0.
Constraints
2≤n≤105.
1≤m≤2⋅105.
Đồ thị liên thông, không có khuyên và không có hai cạnh nối cùng một cặp đỉnh.
Scoring
Subtask 1 (50% số điểm): các test từ 1 đến 10, kích thước nhỏ.
Subtask 2 (50% số điểm): không có giới hạn bổ sung.
Example
Test 1
Input
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
Output
2
3 4
Giải thích: Xóa 3 hoặc 4 làm hai tam giác tách nhau; xóa bất kỳ đỉnh nào khác vẫn để các đỉnh còn lại trong một thành phần.
Lời giải tóm tắt
Phân tích: Một đỉnh là đỉnh khớp khi xóa nó và các cạnh kề làm số thành phần liên thông tăng. Ta dùng tin và low trên cây DFS.
Phân tích: Với đỉnh u không phải gốc, u là đỉnh khớp nếu tồn tại một con DFS v sao cho low[v] ≥ tin[u].
Phân tích: Gốc của một cây DFS là đỉnh khớp đúng khi nó có ít nhất hai con DFS trực tiếp.
Thuật toán: 1. Dựng danh sách kề có mã cạnh để phân biệt chính xác cạnh cha với các cạnh còn lại. 2. Chạy DFS lặp trên đồ thị, gán tin[u], low[u] và đếm số con DFS trực tiếp của từng gốc. 3. Khi kết thúc cây con v của u, cập nhật low[u]. Nếu u không phải gốc và low[v] ≥ tin[u], đánh dấu u. 4. Sau khi kết thúc một cây DFS, đánh dấu gốc nếu nó có ít nhất hai con. Thu các đỉnh đã đánh dấu theo thứ tự tăng và in ra.
Chứng minh tính đúng đắn:Bổ đề 1. Với đỉnh không phải gốc u, nếu có con v thỏa low[v] ≥ tin[u], cây con của v không có đường tránh u để đi tới tổ tiên của u. Xóa u vì thế tách cây con này khỏi phần còn lại.
Chứng minh tính đúng đắn:Bổ đề 2. Nếu mọi con v của đỉnh không phải gốc đều có low[v] < tin[u], mỗi cây con có đường đi qua một cạnh ngược tới tổ tiên của u; sau khi xóa u, các phần còn lại vẫn nối với nhau qua phía trên.
Chứng minh tính đúng đắn:Bổ đề 3. Các cây con DFS trực tiếp của một gốc không có cạnh nối chéo. Do đó xóa gốc chỉ làm tăng số thành phần khi gốc có ít nhất hai con.
Chứng minh tính đúng đắn:Định lý. Ba trường hợp trên là cần và đủ cho mọi đỉnh của cây DFS, nên thuật toán đánh dấu đúng và đủ các đỉnh khớp.