blob: 25ff67ec14fc98719e2afc9982e46e78c0bf05a6 (
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 = sz(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(si + all(st));
st.resize(si);
}}}
return top;
}
void find() {
counter = 0;
num.assign(sz(adj), 0);
isArt.assign(sz(adj), false);
bridges.clear();
st.clear();
bcc.clear();
for (int v = 0; v < sz(adj); v++) {
if (!num[v]) {
root = v;
rootCount = 0;
dfs(v);
isArt[v] = rootCount > 1;
}}}
|
