[学习笔记]强连通分量

定义

什么是强连通分量？直白地说就是在一个有向图中，有一块区域，每个点都可以互相抵达。这里用一张图来说明一下。

图中的 \(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);
	}
}

接下来看几道例题。

例题

P3387 【模板】缩点

强连通分量 + 缩点，先求强连通分量，再进行缩点的过程，最后输出答案。

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;
}

P3627 [APIO2009] 抢掠计划

某次校内模拟赛原题，当时竟然没想到是强连通分量。

像上一题那样，先求强连通分量，再缩点，然后用拓扑排序/某个已死的算法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;
}

习题

暂无。