Mạng đường truyền là đồ thị vô hướng n đỉnh, m cạnh (có thể nhiều thành phần liên thông, có thể có cạnh song song). Cầu là cạnh mà khi bỏ đi sẽ làm tăng số thành phần liên thông.
Dùng thuật toán Tarjan: DFS, duy trì tin[u] (thời điểm thăm) và low[u] (thời điểm sớm nhất tới được). Cạnh (u,v) với v là con DFS là cầu khi low[v]>tin[u]. Lưu ý xử lý cạnh song song: ta theo dõi id cạnh, không phải đỉnh cha.
Hãy đếm số cầu của đồ thị.
Dòng 1: n, m. m dòng tiếp, mỗi dòng hai số u,v.
1≤n≤5000, 0≤m≤2⋅104. Có thể có cạnh song song nhưng không có cạnh tự thân.
Một số nguyên — số cầu.
Ví dụ:
Đầu vào:
5 5
1 2
2 3
3 1
3 4
4 5
Đầu ra:
2
Giải thích:
Đang tải editor...