浅谈 Tarjan 算法之强连通分量（危

引子

果然老师们都只看标签拉题。。。

2020.8.19新初二的题集中出现了一道题目（现已除名），叫做Running In The Sky。

OJ上叫绮丽的天空

发现需要处理环，然后通过一些神奇的渠道了解到有个东西叫缩点。

紧接着搜了一下缩点，发现了 Tarjan 算法。

然后又翻了翻算法竞赛，于是一去不复返……

一些定义

给定一张有向图。对于图中任意两个节点 \(x, y\)，存在从 \(x\) 到 \(y\) 的路径，也存在 \(y\) 到 \(x\) 的路径。则称该有向图为“强连通图”。

有向图的强连通子图被称为强连通分量 \(SCC\) \((Strongly\) \(Connected\) \(Component)\)。

显然，环一定是强连通图。因为如果在有向图中存在 \(x\) 到 \(y\) 的路径，且存在 \(y\) 到 \(x\) 的路径，那么 \(x, y\) 一定在同一个环中。

对于一个有向图，如果从 \(root\) 可以到达图中所有的点，则称其为“流图”，而 \(root\) 为流图的源点。

以 \(root\) 为原点对流图深度优先遍历，每个点只访问一次，在过程中，所有发生递归的边 \((x, y)\) 构成的一棵树叫做这个流图的搜索树。

在深度优先遍历时，对每个访问到的节点分别进行整数 \(1...n\) 标记，该标记被称为时间戳，记为 \(dfn[x]\)。

流图中的每条有向边 \((x, y)\) 必然是以下四种中的一种：

前向边，指搜索树中 \(x\) 是 \(y\) 的祖先节点
后向边，指搜索树中 \(y\) 是 \(x\) 的祖先节点
树枝边，指搜索树里的边，满足 \(x\) 是 \(y\) 的父节点。
其他边（好像也叫横叉边），指除了上面三种情况的边。且一定满足 \(dfn[y] < dfn[x]\)

Tarjan算法之强连通分量

Tarjan 算法基于有向图的深度优先遍历，能够在线性时间中求出一张有向图的各个强连通分量。

其核心思想就是考虑两点之间是否存在路径可以实现往返。

我们在后文中，都会结合搜索树（本身就是深度优先遍历的产物）来考虑，这样就可以在深度优先遍历的同时完成我们的目标。

对于流图，前向边作用不大，因为当前搜索树中一定存在 \(x\) 到 \(y\) 的路径。

后向边就很重要了，因为它一定可以和搜索树中 \(x\) 到 \(y\) 的路径组成环。

横叉边需要判断一下，如果这条横叉边能到达搜索树上 \(x\) 的祖先（显然，\(x\) 的祖先一定可以到达 \(x\)）。记这个祖先为 \(z\)，则这条横叉边一定能和它到 \(z\) 的路径，\(z\) 到 \(x\) 的路径组成环。

为了找到横叉边与后向边组成的环，我们考虑在深度优先遍历的同时维护一个栈。

当遍历到 \(i\) 节点时，栈里一定有以下一些点：

搜索树上 \(i\) 的所有祖先集合 \(j\)。若此时存在后向边 \((i, j)\)，则 \((i, j)\) 一定与 \(j\) 到 \(i\) 的路径形成环。
已经访问过的点 \(k\)，且满足从 \(k\) 出发一定能找到到 \(j\) 的路径。此时，\((i, k)\)，\(k\) 到 \(j\) 的路径，\(j\) 到 \(i\) 的路径一定会形成环。

于是我们引入回溯值的概念。回溯值 \(low[x]\) 表示以下节点的最小时间戳：

该点在栈中。
存在一条从流图的搜索树中以 \(x\) 为根的子树为起点出发的有向边，以该点为终点。（也就是以它为起点能继续往下遍历到的点）

如果当前的 \(low[x]\) 表示的最小时间戳代表的点集全是2类点，则易得 \(low[x] = dfn[x]\) 时强连通分量存在，且 \(x\) 是此强连通分量的根（整个强连通分量中时间戳最小的节点）。

如果表示的点集存在1类点。则当前点一定属于强连通分量，且该强连通分量的根为整个强连通分量中时间戳最小的节点。

当我们判断了存在以当前点为根的强连通分量后，从栈中不断取出点，直到取出的点与当前点相等，我们就得到了整个强连通分量的信息。

整理更新回溯值的方法：

如果当前点第一次被访问，入栈，且 \(low[x] = dfn[x]\)。
遍历从 \(x\) 为起点的每一条边 \((x, y)\)。若 \(y\) 被访问过，且 \(y\) 在栈中，那么 \(low[x] = min(low[x], dfn[y])\)。若 \(y\) 没被访问过，递归访问 \(y\)，在回溯之后更新 \(low[x] = min(low[x], low[y])\)。（典型\(dp\)思想）

具体实现

int dfn[MAXN], low[MAXN];

// 时间戳及回溯值。

vector <int> scc[MAXN];

// 储存最后求出的各个强连通分量的信息。

int key[MAXN];

// key[i]表示i在编号为key[i]的强连通分量中。

stack<int> st; // 栈。

bool vis[MAXN];

// 记录是否在栈中。

int num = 0, cnt = 0;

// num 时间戳标记。cnt 强连通分量标记。

void tarjan(int x) {

	num++;

	dfn[x] = num;

	low[x] = num;

	st.push(x);

	vis[x] = true;

    // 第一次遍历到，记录时间戳，入栈，记录当前回溯值

	for(int i = 0; i < map_first[x].size(); i++) { // 枚举每条边。

		int j = map_first[x][i];

		if(!dfn[j]) { // 如果当前边的终点没被遍历过。

			tarjan(j); // 递归遍历。

			low[x] = min(low[x], low[j]);

            // 维护回溯值。

		}

		else if(vis[j]) // 如果遍历过且在栈中。

			low[x] = min(low[x], dfn[j]);

            // 维护回溯值。

	}

	if(dfn[x] == low[x]) { // 如果存在以当前点为根的强连通分量。

		cnt++;

		int now = 0;

		while(x != now) { // 找出栈中所有在当前强连通分量中的点。

			now = st.top();

			st.pop();

			vis[now] = false;

			key[now] = cnt;	// 存所在编号。

			scc[cnt].push_back(now); // 存点。

		}

	}

}

缩点

缩点。其实就是指的把环看成一个点来进行后面的图论算法。而把环看成的这个点的点权在题目中会具体说明。

比较常见的缩点后的点权是整个环路的所有点的点权和。

如下图：

1 -> 2 -> 4 -> 5 -> 2 -> 3

显然上图存在环路。在经过缩点后，我们可以将它变成这样：

1 -> 2(value[2] + value[4] + value[5]) -> 3

思路比较简单，我就直接分析代码了。。。

具体实现

for(int i = 1; i <= n; i++)

    for(int j = 0; j < map_first[i].size(); j++) {

        // 枚举原图中的每一条边。

        int v = map_first[i][j];

        if(key[i] == key[v])

        // 如果这个边的两端属于同一个强连通分量，则直接放弃这条连边。

            continue;

        map_second[key[i]].push_back(key[v]);

        // 将两个点对应的强连通分量的编号相连，加入新图。

        // 显然，单个点也属于一个强连通分量。

    }

现在，我们再来看看引子中提到的那道题吧。。。

题目描述

一天的活动过后，所有学生都停下来欣赏夜空下点亮的风筝。\(Curtis\) \(Nishikino\)想要以更近的视角感受一下，所以她跑到空中的风筝上去了(这对于一个妹子来说有点匪夷所思)! 每只风筝上的灯光都有一个亮度 \(k_i\). 由于风的作用，一些风筝缠在了一起。但是这并不会破坏美妙的气氛，缠在一起的风筝会将灯光汇聚起来，形成更亮的光源！

\(Curtis\) \(Nishikino\)已经知道了一些风筝间的关系，比如给出一对风筝 \((a,b)\), 这意味着她可以从 \(a\) 跑到 \(b\) 上去，但是不能返回。

现在，请帮她找到一条路径(她可以到达一只风筝多次，但只在第一次到达时她会去感受上面的灯光), 使得她可以感受到最多的光亮。同时请告诉她这条路径上单只风筝的最大亮度，如果有多条符合条件的路径，输出能产生最大单只风筝亮度的答案。

输入格式

第一行两个整数 \(n\) 和 \(m\)。 \(n\) 是风筝的数量, \(m\) 是风筝间关系对的数量。

接下来一行 \(n\) 个整数 \(k_i\)。

接下来 \(m\) 行, 每行两个整数 \(a\) 和 \(b\), 即 \(Curtis\) 可以从 \(a\) 跑到 \(b\)。

输出格式

一行两个整数。\(Curtis\) 在计算出的路径上感受到的亮度和，这条路径上的单只风筝最大亮度。

样例输入

样例输出

41 11

分析

显然这道题是有环的对吧。

如果我们不考虑环的情况，其实就是一个很板白菜的题目。

我们可以采用拓扑排序的思路，遍历整个图，然后对于每个路径维护一下到当前点的最大距离，并维护一个这个路径上的最大值。

然后考虑有环，很简单，事先 Tarjan 缩点嘛/xyx

并且这道题是要累加路径上的点的和。所以缩点后的点就是当前强连通分量包含的所有点的点权和。

AC代码

#include <cstdio>

#include <stack>

#include <queue>

#include <vector>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 200005;

int n, m;

int value[MAXN];

vector<int> map_first[MAXN];

// 原图。

int dfn[MAXN], low[MAXN];

struct data {

	int ma, sum;

	data() {

		ma = 0;

		sum = 0;

	}

	data(int Ma, int S) {

		ma = Ma;

		sum = S;

	}

} scc[MAXN];

// Tarjan 求出的强连通分量中，维护两个信息。

// 1.ma 表示整个强连通分量的最大值。

// 2.sum 表示整个强连通分量的点权和，即缩点后的点权。

int key[MAXN];

stack<int> st;

bool vis[MAXN];

int num = 0, cnt = 0;

void tarjan(int x) { // tarjan 算法。

	num++;

	dfn[x] = num;

	low[x] = num;

	st.push(x);

	vis[x] = true;

	for(int i = 0; i < map_first[x].size(); i++) {

		int j = map_first[x][i];

		if(!dfn[j]) {

			tarjan(j);

			low[x] = min(low[x], low[j]);

		}

		else if(vis[j])

			low[x] = min(low[x], dfn[j]);

	}

	if(dfn[x] == low[x]) {

		cnt++;

		int now = 0;

		while(x != now) {

			now = st.top();

			st.pop();

			vis[now] = false;

			key[now] = cnt;

			scc[cnt].ma = max(scc[cnt].ma, value[now]);

			scc[cnt].sum += value[now];

			// 维护一下强连通分量的两个信息。

		}

	}

}

vector<int> map_second[MAXN]; // 新图。

int in[MAXN]; // 拓扑排序，统计点的入度。

int dp[MAXN][2];

// dp[i][0]表示到i点的最长路径。

// dp[i][1]表示路径上的最大点权。 

void T_Sort() { // 拓扑。

	queue<int> q;

	for(int i = 1; i <= cnt; i++) {

		dp[i][0] = scc[i].sum;

		dp[i][1] = scc[i].ma;

	}

	for(int i = 1; i <= cnt; i++)

		if(!in[i])

			q.push(i);

	while(!q.empty()) {

		int x = q.front();

		q.pop();

		for(int i = 0; i < map_second[x].size(); i++) {

			int v = map_second[x][i];

			in[v]--;

			if(!in[v])

				q.push(v);

			if(dp[v][0] < dp[x][0] + scc[v].sum) {

				dp[v][0] = dp[x][0] + scc[v].sum;

				dp[v][1] = max(dp[x][1], scc[v].ma);

				// 更新最长路径及最大点权。

			}

			if(dp[v][0] == dp[x][0] + scc[v].sum)

				dp[v][1] = max(dp[v][1], dp[x][1]);

			// 如果有两条最长路径则记录两条路径中的最大值。

		}

	}

}

int main() {

	scanf ("%d %d", &n, &m);

	for(int i = 1; i <= n; i++) {

		scanf ("%d", &value[i]);

		key[i] = i;

	}

	for(int i = 1; i <= m; i++) {

		int u, v;

		scanf ("%d %d", &u, &v);

		map_first[u].push_back(v);

	}

	for(int i = 1; i <= n; i++)

		if(!dfn[i]) // 如果当前点没被遍历，则跑一遍 Tarjan。

			tarjan(i); 

	for(int i = 1; i <= n; i++)

		for(int j = 0; j < map_first[i].size(); j++) {

			int v = map_first[i][j];

			if(key[i] == key[v])

				continue;

			map_second[key[i]].push_back(key[v]);

			in[key[v]]++;

		}

	// 缩点，存新图。 

	T_Sort();

	int ans = 1;

	for(int i = 2; i <= cnt; i++) // 统计答案。

		if(dp[i][0] > dp[ans][0] || (dp[i][0] == dp[ans][0] && dp[i][1] > dp[ans][1]))

			ans = i;

	printf("%d %d", dp[ans][0], dp[ans][1]);

	return 0;

}

巴特西