定义
什么是强连通分量？直白地说就是在一个有向图中，有一块区域，每个点都可以互相抵达。这里用一张图来说明一下。
图中的 \(1, 2, 3\) 是一个强连通分量，因为他们可以互相抵达。
Tarjan 算法
如何求强连通分量，最有名且最常用的就是 Tarjan 算法。
先给出如下定义：
- \(dfn_u\)：深搜时被第几个遍历，称为时间戳。
- \(low_u\)：在 \(u\) 的子树中能回溯到的最早在栈中的节点。
分 3 种情况考虑：
- 当 \(v\) 未被访问，那么就继续访问，同时更新 \(low_u\) 。
- 当 \(v\) 被访问过，且在栈当中，用 \(dfn_v\) 更新 \(low_u\) 。
- 当 \(v\) 被访问过，且不在栈中，说明已经处理完毕，不用继续处理。
同时，如果在回溯中 \(dfn_u = low_u\) ，说明栈中 \(u\) 和它上方的节点构成强连通分量。
接下来给出模板代码
struct Edge{
int v, nxt;
}edge[N];
int head[N], dfn[N], low[N], col[N], v[N], sum[N];
// 强连通分量编号，点权，强连通分量点权
void Tarjan(int u)
{
dfn[u] = low[u] = ++indx; st.push(u);
for (int i = head[u]; i; i = edge[i].nxt)
{
int v = edge[i].v;
if (!dfn[v]){Tarjan(v); low[u] = min(low[u], low[v]);}
else if (!col[v])low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
tot++;
int x;
do{
x = st.top(); st.pop(); col[x] = tot; sum[tot] += v[x];
}while (x != u);
}
}
接下来看几道例题。
例题
强连通分量 + 缩点，先求强连通分量，再进行缩点的过程，最后输出答案。
Accepted Code
/*上古时期写的，不知链式前向星*/
#include <bits/stdc++.h>
using namespace std;
const int N = 114514;
vector<int> edge[N];
vector<int> newG[N];
int f[N], dfn[N], low[N], col[N], W[N], sum[N], ru[N], st[N], que[N], ans;
int inde, tot, top, qr;
void add_edge(int u, int v){edge[u].push_back(v);}
void tarjan(int u)
{
dfn[u] = low[u] = ++inde;
st[++top] = u;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i];
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (!col[v])low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
col[u] = ++tot;
sum[tot] += W[u];
int x;
while (x = st[top--], x != u)col[x] = tot, sum[tot] += W[x];
}
}
int main()
{
int n, m, i, j, u, v, x;
cin >> n >> m;
for (i = 1; i <= n; i++)cin >> W[i];
for (i = 1; i <= m; i++)
{
cin >> u >> v;
add_edge(u, v);
}
for (i = 1; i <= n; i++)if (!dfn[i])tarjan(i);
for (i = 1; i <= n; i++)
for (j = 0; j < edge[i].size(); j++)
{
x = edge[i][j];
if (col[i] != col[x])newG[col[i]].push_back(col[x]), ru[col[x]]++;
}
for (i = 1; i <= tot; i++)
if (!ru[i])que[++qr] = i, f[i] = sum[i];
for (i = 1; i <= qr; i++)
{
u = que[i];
for (int j = 0; j < newG[u].size(); j++)
{
v = newG[u][j];
f[v] = max(f[v], f[u] + sum[v]);
if (!--ru[v])que[++qr] = v;
}
}
for (i = 1; i <= tot; i++)ans = max(ans, f[i]);
cout << ans;
return 0;
}
某次校内模拟赛原题，当时竟然没想到是强连通分量。
像上一题那样，先求强连通分量，再缩点，然后用拓扑排序/某个已死的算法SPFA，求出一条最长路，答案为 \(\max\limits_{1 \le i \le p}\{dis_{col_{t_i}}\}\)
Accepted Code
/*Code By Manipula*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
struct Edge{
int v, nxt;
}edge1[N], edge2[N];
stack<int> st;
int head1[N], head2[N], dfn[N], low[N], rn[N], col[N], v[N], t[N], sum[N], dis[N];
int indx, num1, num2, tot, n, m, s, p, ans;
void add1(int u, int v){edge1[++num1] = (Edge){v, head1[u]}; head1[u] = num1;}
void add2(int u, int v){edge2[++num2] = (Edge){v, head2[u]}; head2[u] = num2;}
int find(int u, int v)
{
for (int i = head2[u]; i; i = edge2[i].nxt)
if (v == edge2[i].v)return 1;
return 0;
}
void Tarjan(int u)
{
dfn[u] = low[u] = ++indx; st.push(u);
for (int i = head1[u]; i; i = edge1[i].nxt)
{
int v = edge1[i].v;
if (!dfn[v]){Tarjan(v); low[u] = min(low[u], low[v]);}
else if (!col[v])low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
tot++;
int x;
do{
x = st.top(); st.pop(); col[x] = tot; sum[tot] += v[x];
}while (x != u);
}
}
void toposort()
{
queue<int> q;
memset(dis, -0x3f3f3f3f, sizeof(dis));
for (int i = 1; i <= tot; i++)if (!rn[i])q.push(i);
dis[col[s]] = sum[col[s]];
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = head2[u]; i; i = edge2[i].nxt)
{
int v = edge2[i].v;
dis[v] = max(dis[v], dis[u] + sum[v]);
if (--rn[v] == 0)q.push(v);
}
}
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
add1(u, v);
}
for (int i = 1; i <= n; i++)cin >> v[i];
cin >> s >> p;
for (int i = 1; i <= p; i++)cin >> t[i];
for (int i = 1; i <= n; i++)if (!dfn[i])Tarjan(i);
for (int i = 1; i <= n; i++)
for (int j = head1[i]; j; j = edge1[j].nxt)
{
int v = edge1[j].v;
if (col[i] != col[v] && !find(col[i], col[v]))
add2(col[i], col[v]), rn[col[v]]++;
}
toposort();
for (int i = 1; i <= p; i++)ans = max(ans, dis[col[t[i]]]);
cout << ans;
return 0;
}
习题
暂无。