-
Notifications
You must be signed in to change notification settings - Fork 1
/
TarjanBridges.cpp
67 lines (57 loc) · 1.61 KB
/
TarjanBridges.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
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using Gr = vector<vector<int>>;
struct TarjanBridges {
vector<int> num, low;
int at = 1;
// you can also store edge ids
// important if you have parallel edges
vector<ii> edges;
vector<int> art;
void dfs(Gr const& g, int u, int p = -1) {
num[u] = low[u] = at++;
int nchild = 0;
for (int v : g[u]) {
// if graph has parallel edged you should assing an id to every edge
// and in the next line check if the edge id is the same as the parent edge
if (v == p) continue;
if (num[v] != 0) {
low[u] = min(low[u], num[v]);
continue;
}
dfs(g, v, u);
low[u] = min(low[u], low[v]);
nchild++;
if (low[v] > num[u]) {
edges.emplace_back(u, v);
}
if (p != -1 and low[v] >= num[u]) {
art[u] = 1;
}
}
if (p == -1 and nchild > 1) art[u] = 1;
}
// 0 indexed please
TarjanBridges(Gr const& g) : num(g.size()), low(g.size()), art(g.size()) {
int n = g.size();
for (int i = 0; i < n; i++) {
if (num[i] == 0) {
dfs(g, i);
}
}
}
vector<int> get_articulations() {
int n = num.size();
vector<int> ans;
for (int i = 0; i < n; i++) {
if (art[i]) {
ans.push_back(i);
}
}
return ans;
}
vector<ii> get_bridges() {
return edges;
}
};