/
tarjan.h
131 lines (115 loc) · 2.46 KB
/
tarjan.h
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#pragma once
#include "../utils/template.h"
/**
* @brief Tarjan's algorithm
* @docs docs/tarjan.md
*/
struct SCC {
int n, t, ii;
vector<vector<int>> adj;
vector<int> dfn, low, id;
vector<bool> ins;
stack<int> stk;
vector<vector<int>> comps;
SCC(int mm) : n(mm), t(0), ii(0), adj(mm), dfn(mm), low(mm), id(mm), ins(mm) {}
void addedge(int a, int b) {
adj[a].emplace_back(b);
}
void dfs(int cur) {
dfn[cur] = low[cur] = ++t;
stk.push(cur);
ins[cur] = 1;
for (int u: adj[cur]) {
if (!dfn[u]) {
dfs(u);
low[cur] = min(low[cur], low[u]);
}
else if (ins[u])
low[cur] = min(low[cur], dfn[u]);
}
if (dfn[cur] == low[cur]) {
int u = -1;
comps.emplace_back();
while (u != cur) {
u = stk.top(); stk.pop();
ins[u] = 0;
id[u] = cur;
comps.back().emplace_back(u);
}
}
}
void run() {
for (int i = 0; i < n; i++) {
if (!dfn[i]) {
dfs(i);
}
}
}
};
// Any connected graph decomposes into a tree of **biconnected components (BCCs)** called the **block-cut** tree of the graph
struct blockcut {
int n, t, ei, ncomps;
vector<vector<pii>> adj;
vector<vector<int>> adj2, comps;
vector<int> dfn, low, id;
vector<bool> ins;
stack<int> st;
set<int> art;
blockcut(int mm) : n(mm), t(0), ei(0), ncomps(0), adj(mm), comps(mm), dfn(mm), low(mm), id(mm), ins(mm) {}
void addedge(int a, int b) {
adj[a].emplace_back(b, ei);
adj[b].emplace_back(a, ei);
ei++;
}
void process(int cur){
if (st.empty()) return;
while (st.size()) {
int u = st.top(); st.pop();
comps[ncomps].push_back(u);
if (u == cur)
break;
}
ncomps++;
}
void dfs(int cur, int pi = -1) {
dfn[cur] = low[cur] = ++t;
st.push(cur);
int ch = 0;
for (auto [u, i]: adj[cur]) {
if (i == pi) continue;
if (!dfn[u]) {
ch++;
dfs(u, i);
low[cur] = min(low[cur], low[u]);
if ((pi == -1 and ch > 1) or (pi != -1 and low[u] >= dfn[cur])) {
art.insert(cur);
st.push(cur);
process(u);
}
}
else
low[cur] = min(low[cur], dfn[u]);
}
}
// Block leaders are numbered [n, n + ncomps)
int run() {
for (int i = 0; i < n; i++) {
if (!dfn[i]) {
dfs(i, -1);
st.push(i);
process(-1); // pop stack until empty
}
}
comps.resize(ncomps);
adj2.resize(n+ncomps);
for (int i = 0; i < ncomps; i++) {
sort(all(comps[i]));
makeunique(comps[i]);
for (int u: comps[i]) {
adj2[n+i].push_back(u);
adj2[u].push_back(n+i);
}
}
return n + ncomps;
}
};