「学习笔记」tarjan

$tarjan$ 是可以求图中的 $SCC$ 的算法，时间复杂度 $O(n + m)$。以下是如何求图中的 $SCC$。

$tarjan$ 算法基于对图的深度优先搜索，在搜索过程中，维护一个栈，每次把搜索树中未处理的点压入栈。

算法中维护了以下几个变量：

• $dfn$：为 $u$ 在搜索树中被搜索的次序。

• $low$ 为当前节点在子树中最小的 不在搜索树上的一个节点 的 $dfn$。

一个节点子树内的 $dfn$ 都小于这个点的 $dfn$。

基于图中的深度优先搜索的次序，维护 $dfn$ 和 $low$ 这两个数组，让搜索的节点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。

在搜索过程中，每个节点考虑 $3$ 中情况：

1. 当 $v$ 未被访问过的时候，即 !dfn[v]，继续对 $v$ 进行搜索，然后用 $low_v$ 来更新 $low_u$。因为存在从 $u$ 到 $v$ 的直接路径，所以 $v$ 能够回溯到的已经在栈中的结点，$u$ 也一定能够回溯到。

2. 当 $v$ 被访问过的时候，用 $dfn_v$ 更新 $low_u$。

3. $v$ 被访问过，已不在栈中：说明 $v$ 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

Code:

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 5;
typedef long long ll;int head[maxn], cnt, head2[maxn], cnt2;
struct edge { int to, nxt; } e[maxn], g[maxn];void add(int u, int v) {e[++ cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt;
}void add2(int u, int v) {g[++ cnt2].to = v;g[cnt2].nxt = head2[u];head2[u] = cnt2;
}int n, m, a[maxn], u[maxn], v[maxn];
int stk[maxn], top;
int dfn[maxn], low[maxn], fa[maxn], tim;
bool vis[maxn];
queue <int> q;
int f[maxn], in[maxn];void tarjan(int u) {dfn[u] = low[u] = ++tim;vis[stk[++ top] = u] = 1;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);else if (vis[v]) low[u] = min(low[u], dfn[v]);}if (low[u] == dfn[u]) {do {vis[stk[top]] = 0;fa[stk[top]] = u;if (u != stk[top]) a[u] += a[stk[top]];} while (stk[top--] != u);}
}int main() {// freopen("123.in", "r", stdin);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= m; i++) scanf("%d%d", &u[i], &v[i]), add(u[i], v[i]);for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);for (int i = 1; i <= m; i++) {int x = fa[u[i]], y = fa[v[i]];if (x != y) add2(x, y), in[y] ++;}for (int i = 1; i <= n; i++) {if (!in[i] && i == fa[i]) q.push(i), f[i] = a[i];}while (!q.empty()) {int u = q.front();q.pop();for (int i = head2[u]; i; i = g[i].nxt) {int v = g[i].to;f[v] = max(f[u] + a[v], f[v]);if (!--in[v]) q.push(v);}}int res = 0;for (int i = 1; i <= n; i++) res = max(res, f[i]);cout << res << '\n';return 0;
}