-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSCC.cpp
More file actions
35 lines (35 loc) · 779 Bytes
/
SCC.cpp
File metadata and controls
35 lines (35 loc) · 779 Bytes
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
#include <bits/stdc++.h>
using namespace std;
// 邻接表, 强连通分量集合
vector<vector<int>> g, sccs;
vector<int> dfn, low;
// 是否在栈中, 即是否在搜索路径中
vector<bool> instk;
// 路径上的点压栈
stack<int> stk;
// 当前访问时间戳
int tot;
// tarjan算法求强连通分量
void tarjan(int u) {
dfn[u] = low[u] = tot++;
stk.push(u);
instk[u] = true;
for (auto v : g[u]) {
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] != low[u]) return;
// 该点是强连通分量的根
sccs.push_back({});
int v;
do {
v = stk.top();
stk.pop();
instk[v] = false;
sccs.back().push_back(v);
} while (v != u);
}