Bài toán
Liệt kê các cầu trong đồ thị vô hướng.
Độ phức tạp
O(m+n)
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000006
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)
typedef pair<int, int> ii;
int n, m, cnt=0;
vector<int> a[N]; //
int Visited[N], Low[N], Parent[N]; //
vector<pair<int, int> > Bridge; //
bool minimize(int &a, int b) { if (a>b) a=b; else return false; return true; }
void visit(int u){
Low[u]=Visited[u]=++cnt;
for (int i=0,v; v=a[u][i]; i++)
if (v!=Parent[u]){
if (Visited[v]) minimize(Low[u], Visited[v]);
else {
Parent[v]=u; visit(v); minimize(Low[u], Low[v]);
if (Low[v]>=Visited[v]) Bridge.push_back(ii(u,v));
}
}
}
main(){
ios :: sync_with_stdio(false);
cin >> n >> m;
f1(i,m) {
int p, q;
cin >> p >> q;
a[p].push_back(q);
a[q].push_back(p);
}
f1(i,n) a[i].push_back(0);
f1(i,n) if (!Visited[i]) visit(i);
cout << Bridge.size() << " critical links" << endl;
f0(i,Bridge.size()) cout << Bridge[i].first << " " << Bridge[i].second << endl;
cin.ignore(2);
}
Nhận xét
Code này có thể chạy được với đồ thị không liên thông, tuy nhiên không chạy được trên đa đồ thị.
Ví dụ
8 6
1 2
2 3
2 4
3 4
4 5
7 8
3 critical links
4 5
1 2
7 8