Cho một đơn đồ thị vô hướng liên thông. Hãy tìm tất cả các cạnh mà khi xóa riêng cạnh đó, đồ thị không còn liên thông.
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 cạnh cần thiết k.
K dòng sau in hai đầu mút của từng cạnh, đầu nhỏ trước; các cặp được sắp tăng theo thứ tự từ điển.
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
1
3 4
Giải thích: Hai tam giác vẫn liên thông nếu bỏ một cạnh nội bộ, còn cạnh 34 là đường nối duy nhất giữa hai khối nên phải được in.
Lời giải tóm tắt
Phân tích: Một cạnh vô hướng là cầu khi xóa cạnh đó làm số thành phần liên thông tăng. Ta duyệt DFS và lưu:
Phân tích:tin[u]: thời điểm đỉnh u được thăm;
Phân tích:low[u]: thời điểm nhỏ nhất của một đỉnh mà cây con DFS của u có thể đi tới bằng các cạnh cây rồi dùng nhiều nhất một cạnh ngược.
Phân tích: Với cạnh cây từ u xuống v, cạnh đó là cầu đúng khi low[v] > tin[u].
Thuật toán: 1. Lưu mỗi cạnh với một mã riêng và đưa mã đó vào danh sách kề của cả hai đầu mút. 2. Chạy DFS lặp bằng các frame (u, cạnh-cha, vị trí-kề-tiếp-theo). Khi gặp đỉnh mới, gán tin và low; khi gặp cạnh đã thăm không phải cạnh cha, cập nhật low[u] bằng tin[v]. 3. Khi hoàn tất cây con của v, cập nhật low[u] = min(low[u], low[v]). Nếu low[v] > tin[u], ghi nhận cạnh (u,v) là cầu. 4. Chuẩn hóa mỗi cặp đầu mút thành (min(u,v), max(u,v)), sắp tăng và in kết quả.
Chứng minh tính đúng đắn:Bổ đề 1. Nếu low[v] > tin[u], không có cạnh nào từ cây con DFS của v đi tới u hoặc một tổ tiên của u. Vì thế mọi đường từ cây con này ra phần còn lại đều phải dùng cạnh (u,v); xóa cạnh đó làm đồ thị bị tách.
Chứng minh tính đúng đắn:Bổ đề 2. Nếu low[v] ≤ tin[u], từ cây con của v có một cạnh ngược đi tới u hoặc tổ tiên của u. Cạnh ngược cùng các cạnh cây tạo một đường thay thế, nên xóa (u,v) không làm mất liên thông.
Chứng minh tính đúng đắn:Định lý. Mọi cạnh không phải cạnh cây nằm trên một chu trình với đường cây DFS nên không thể là cầu. Kết hợp hai bổ đề, thuật toán ghi nhận đúng và đủ mọi cầu; bước chuẩn hóa chỉ thay đổi thứ tự biểu diễn.
Độ phức tạp: Thời gian O(n+m+b log b), trong đó b là số cầu; bộ nhớ O(n+m). Phần DFS riêng có thời gian O(n+m).