scc tarjan + 缩点
sccc_
·
·
个人记录
强连通分量（scc）
定义
强连通：在有向图 G 中，两个不同的顶点 u,v，即存在 u 到 v 的有向路径，也存在 v 到 u 的有向路径，则称两个顶点是强连通的。
弱连通：忽略有向图中的方向，如果得到的无向图是连通的，那么原本的图就是弱联通的。
强连通图：在有向图 G 中，如果每两个节点都相互可达，则称 G 是一个强连通图。
强连通分量：在有向图中最大的一个强连通子图，子图本身是强连通图，且无法再增加原图中其他任何点。
Tarjan
维护一个栈，以及下列几个变量。
$low_i$ 表示点 $i$ 能回溯到的时间戳最小的节点，且在栈中。
$vis_i$ 表示点 $i$ 是否已入栈。
***
### 实现步骤
首先，给当前节点的 $dfn_u$ 分配时间戳 $tim$，$low_u$ 初始值与 $dfn_u$ 相同。将当前节点入栈，标记 $vis_u = 1$。
接下来，枚举当前节点能到达的点 $v$。如果 $dfn_v$ 还没有被分配过时间戳，继续递归到点 $v$，因为返回后 $v$ 的 $low$ 值可能更小，所以更新 $low_u = \min(low_u, low_v)$。否则，判断 $v$ 是否入栈，即判断 $vis_v$ 是否为 $1$，若是，更新 $low_u = \min(low_u, dfn_v)$。
最后，判断当前节点是否为强连通分量的入口。当 $dfn_u = low_u$ 时，证明 $u$ 是这个强连通分量的入口，弹出栈内所有元素，将栈顶元素的入栈标记清空，这些栈内的元素构成了一个 scc。
```c++
void tarjan(int u) {
stk.push(u);
vis[u] = 1;
dfn[u] = low[u] = ++tim;
for (int v : nbr[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(dfn[v], low[u]);
}
}
if (dfn[u] == low[u]) {
while (!stk.empty()) {
vis[stk.top()] = 0;
if (u == stk.top()) {
stk.pop();
break;
}
stk.pop();
}
}
}
```
***
### [B3609 [图论与代数结构 701] 强连通分量](https://www.luogu.com.cn/problem/B3609)
在原来的基础上，为其每一个 scc 染色，以及存储当前 scc 内的节点，以便后面输出。
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m, dfn[N], low[N], col[N], scc, tim;
bool vis[N];
stack<int> stk;
vector<int> nbr[N], v[N];
void tarjan(int u) {
stk.push(u);
vis[u] = 1;
dfn[u] = low[u] = ++tim;
for (int v : nbr[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(dfn[v], low[u]);
}
}
if (dfn[u] == low[u]) {
++scc;
while (!stk.empty()) {
col[stk.top()] = scc;
vis[stk.top()] = 0;
v[scc].push_back(stk.top());
if (u == stk.top()) {
stk.pop();
break;
}
stk.pop();
}
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
nbr[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0)
tarjan(i);
}
cout << scc << '\n';
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0)
continue;
sort(v[col[i]].begin(), v[col[i]].end());
for (auto it : v[col[i]]) {
cout << it << ' ';
dfn[it] = 0;
}
cout << '\n';
}
return 0;
}
```
***
### [P2661 [NOIP 2015 提高组] 信息传递](https://www.luogu.com.cn/problem/P2661)
因为每个点只有一条出边，所以最大的强连通分量会是一个环。
所以只需要记录不是一个点的强连通分量个数即可。
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, dfn[N], low[N], col[N], scc, tim, siz[N];
bool vis[N];
stack<int> stk;
vector<int> nbr[N], v[N];
void tarjan(int u) {
stk.push(u);
vis[u] = 1;
dfn[u] = low[u] = ++tim;
for (int v : nbr[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(dfn[v], low[u]);
}
}
if (dfn[u] == low[u]) {
++scc;
while (!stk.empty()) {
col[stk.top()] = scc;
vis[stk.top()] = 0;
v[scc].push_back(stk.top());
siz[scc]++;
if (u == stk.top()) {
stk.pop();
break;
}
stk.pop();
}
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
nbr[x].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])
tarjan(i);
}
int ans = 1e9;
for (int i = 1; i <= n; i++) {
if (v[col[i]].size() > 1)
ans = min(ans, int(v[col[i]].size()));
}
cout << ans;
return 0;
}
```
***
### [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387)
缩点其实就是将每一个强连通分量都变成一个点，形成一个 DAG。
定义 $sum_i$ 为第 $i$ 个 scc 里点权的和。
我们只要在弹出栈元素的时候求 $sum$，然后后面进行树形 dp 即可。
```c++
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, m, dfn[N], low[N], col[N], scc, tim, sum[N], dp[N], a[N], in[N];
bool vis[N];
stack<int> stk;
vector<int> nbr[N], new_nbr[N];
pair<int, int> g[N];
void tarjan(int u) {
stk.push(u);
vis[u] = 1;
dfn[u] = low[u] = ++tim;
for (int v : nbr[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(dfn[v], low[u]);
}
}
if (dfn[u] == low[u]) {
++scc;
while (!stk.empty()) {
col[stk.top()] = scc;
vis[stk.top()] = 0;
sum[scc] += a[stk.top()];
if (u == stk.top()) {
stk.pop();
break;
}
stk.pop();
}
}
}
void dfs(int u) {
if (dp[u] != -1)
return;
dp[u] = sum[u];
int maxn = 0;
for (int v : new_nbr[u]) {
if (dp[v] == -1){
dfs(v);
}
maxn = max(maxn, dp[v]);
}
dp[u] += maxn;
return;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
nbr[u].push_back(v);
g[i] = {u, v};
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])
tarjan(i);
}
for (int i = 1; i <= m; i++) {
if (col[g[i].first] != col[g[i].second])
new_nbr[col[g[i].first]].push_back(col[g[i].second]);
}
fill (dp + 1, dp + 1 + n, -1);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dp[i] == -1) {
dfs(i);
ans = max(ans, dp[i]);
}
}
cout << ans;
return 0;
}
```
||scc缩点|并查集缩点|edcc（边双缩点）|
|:-:|:-:|:-:|:-:|
|适用图|有向图|无向图|无向图|
|缩点之后得到的图的类型|DAG|无向森林（多棵树）|连通图之中直接变成一棵树|
|一般求解的问题|拓扑+dp、2-SAT、环路分析|欧拉回路、最小生成树|树形 dp|