-
Notifications
You must be signed in to change notification settings - Fork 0
/
bridgeTree.cpp
72 lines (68 loc) · 1.75 KB
/
bridgeTree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/* bridge tree */
const int MAXN = 1e5+5;
vector<int> adj[MAXN], tree[MAXN]; // The bridge edge tree formed from the given graph.
int disc[MAXN], low[MAXN], vis[MAXN];
queue<int> Q[MAXN];
int currTime, n, m, cmpno = 1;
map<pair<int, int>, int> bridge;
void dfs0(int u, int parent){
vis[u] = true;
disc[u] = low[u] = currTime++;
for(auto v : adj[u]){
if(v == parent) continue;
if(!vis[v]){
dfs0(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > disc[u]){
bridge[{u, v}] = 1;
bridge[{v, u}] = 1;
}
}else{
low[u] = min(low[u], disc[v]);
}
}
return;
}
bool isBridge(int u, int v){
return (bridge[{u, v}] == 1 && bridge[{v, u}] == 1);
}
void dfs1(int u){
int currcmp = cmpno;
Q[currcmp].push(u);
vis[u] = true;
while(!Q[currcmp].empty()){
int u = Q[currcmp].front();
Q[currcmp].pop();
for(auto v : adj[u]){
if(vis[v]) continue;
if(isBridge(u, v)){
cmpno++;
tree[currcmp].push_back(cmpno);
tree[cmpno].push_back(currcmp);
dfs1(v);
}else{
Q[currcmp].push(v);
vis[v] = true;
}
}
}
return;
}
int main(){
io;
cin >> n >> m;
for(int i = 0;i < m; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs0(1, -1); // To find bridges
memset(vis, false, sizeof vis);
dfs1(1); // To build bridge tree
for(int i = 1;i <= cmpno; i++){
for(int j = 0;j < tree[i].size(); j++)
cout << i << " " << tree[i][j] << endl;
}
return 0;
}