blob: 60970e69cc4094fc36b81b040c5842391945a540 (
plain)
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
|
vector<vector<Edge>> adj;
vector<int> num;
int counter, rootCount, root;
vector<bool> isArt;
vector<Edge> bridges, st;
vector<vector<Edge>> bcc;
int dfs(int v, int from = -1) {
int me = num[v] = ++counter, top = me;
for (Edge& e : adj[v]) {
if (e.id == from) continue;
if (num[e.to]) {
top = min(top, num[e.to]);
if (num[e.to] < me) st.push_back(e);
} else {
if (v == root) rootCount++;
int si = ssize(st);
int up = dfs(e.to, e.id);
top = min(top, up);
if (up >= me) isArt[v] = true;
if (up > me) bridges.push_back(e);
if (up <= me) st.push_back(e);
if (up == me) {
bcc.emplace_back(begin(st) + si, end(st));
st.resize(si);
}}}
return top;
}
void find() {
counter = 0;
num.assign(ssize(adj), 0);
isArt.assign(ssize(adj), false);
bridges.clear();
st.clear();
bcc.clear();
for (int v = 0; v < ssize(adj); v++) {
if (!num[v]) {
root = v;
rootCount = 0;
dfs(v);
isArt[v] = rootCount > 1;
}}}
|
