当前位置：首页 > news >正文

Tarjan专题

news 2026/5/11 23:41:49

Tarjan 算法原理

如下图所示。左边是最初的有向图，右边是经过 tarjan 算法后的图，其中实线有向边为树边；虚线有向边为回边；左图存在而右图不存在的边为弃边；每个结点旁边的数字为 dfn 序号。

树边、回边和弃边更精确的定义：

树边：dfs 过程中，从 \(u\) 到达 \(v\)，\(v\) 未被分配 dfn 序号。
回边：dfs 过程中，从 \(u\) 到达 \(v\)，\(v\) 已分配 dfn 序号，但 \(v\) 还未被分配到某个强连通分量中。
弃边：dfs 过程中，从 \(u\) 到达 \(v\)，\(v\) 已分配 dfn 序号，且 \(v\) 已分配到某个强连通分量中。

所有结点和所有树边形成一棵 dfs 树；其中每个点引出的回边都会指向某个 dfn 序更小的结点；弃边没有用。

每个结点遍历完所有出边之后，比较该结点的 dfn 与 low 值是否相等。若相等则需要结算强连通分量。

要烂熟 low 数组的定义！！！

关于 tarjan 算法的疑难杂症：回边情况下 low 值的更新语句。两种不同的写法，会导致 \(low[u]\) 的定义不同。

两种写法都正确，都可以正确地处理出所有强连通分量。但第一种写法的 low 数组定义更明确，即使第二种写法看起来更简便一些，还是推荐使用第一种写法，对理解整个 tarjan 算法的帮助更大，唯一的缺点就是多敲了几下代码。

SCC缩点

// SCC缩点
vector<int> G[N];
int dfn[N],tim;
int low[N]; //low[u]: u及u的子树内的所有点，最多经过一条回边，能够到达的dfn序号最小的点（最上方的点）
int stk[N],top; //栈维护已经遍历过但还未被结算倒某个强连通分量内的结点
int scc[N],cnt_scc; //scc[u]==x表示结点u在第x个强连通分量中, cnt_scc表示当前强连通分量的个数
int siz[N]; //siz[i]表示第i个强连通分量内点的个数void Tarjan_scc(int u)
{dfn[u] = low[u] = ++tim;stk[++top] = u;for(auto v : G[u]){if(!dfn[v]){ // (u, v) 是树边Tarjan_scc(v);low[u] = min(low[u], low[v]); // 注意上面还有一句递归，此时 low[v] 已计算完。low 数组维护的是子树内往上走可到达 dfn 序号最小的点，因此要和儿子 v 的 low 取 min。}else if(!scc[v]){ // (u, v) 是回边low[u] = min(low[u], dfn[v]); // 与上面的区别在于不触发递归，直接利用回边指向的点的 dfn 序号更新当前结点的 low 值。}// else{} // (u, v) 是弃边}if(dfn[u] == low[u]){ // 扎起了口袋，开始结算强连通分量cnt_scc++;int x; //表示栈顶元素，每次弹出的点均属于同一个强连通分量do{x = stk[top--];scc[x] = cnt_scc;siz[cnt_scc] ++;} while(x != u);}
}// 调用
for(int i = 1; i <= n; i ++){if(!dfn[i]) Tarjan_scc(i);
}

P1073

SCC缩点结合 spfa 求最长路

code

P2272

半连通图定义：对于图中的任意两点 \(u, v\)，\(u\)可达\(v\) 或 \(v\)可达\(u\)。

关于半连通图有一个重要的性质：缩点后一定是一条链。

因此计算最大半连通子图的大小，等价于在缩点后的图中求最长链，直接 \(dp\) 即可。

定义 \(dp_{u}\)：以 \(u\) 为终点的最长链长度；\(cnt_{u}\)：以 \(u\) 为终点的最长链数量。状态转移见 code。

注意缩点后的重边会对最长链数量的计算和拓扑排序产生影响，因此需要对缩点后的重边去重。

code

P2515

SCC缩点结合树上背包

与树上带依赖的01背包这个问题相比，只是多了依赖关系可能形成环的可能性。显然我们可以将整个环的所有物品看作是一个物品，于是 \(scc\) 缩点之后的图仍然是若干棵树，问题便与上述等价。

code

P3275

SCC缩点结合差分约束

Q：一共 \(n\) 个数，每个数至少 \(\geq 1\)。要求这 \(n\) 个数满足以下 \(5\) 种类型的共 \(m\) 条约束：

\(1\space u\space v\)：\(u = v\)
\(2\space u\space v\)：\(u < v\)
\(3\space u\space v\)：\(u \ge v\)
\(4\space u\space v\)：\(u > v\)
\(5\space u\space v\)：\(u \le v\)

求所有数总和的最小值，无解输出 -1。

考虑图论建模，利用差分约束的经典建图方式：设 \(u \rightarrow v\)，边权为 \(w\)，表示 \(v - u \ge w\)。

于是以上 \(5\) 种约束均可体现为在图中的有向边，形成 \(n\) 个点 \(m\) 条边的有向图。

显然，对于图中的任何一个环，环中的所有边必须全为 \(0\)，否则无解。

剩下的所有环，包含的所有边的边权均为 \(0\)，等价于该环内所有数均相同。于是缩点后，强连通分量中的所有点等价于一个点，只需要记录它的大小。对于缩点形成的 DAG，将所有入度为 \(0\) 的点置为 \(1\)，然后拓扑排序 dp 即可。具体实现见 code。

code

P4819

SCC缩点结合高难度思维分析

Q：\(n\) 个人，其中有 \(1\) 个人是杀手，他们谁是杀手的概率是相等的。给出若干 \(x \rightarrow y\)，表示第 \(x\) 个人知晓第 \(y\) 个人的身份，且知晓身份具有传递性（\(a\) 知晓 \(b\) 的身份，\(b\) 知晓 \(c\) 的身份，则 \(a\) 知晓 \(c\) 的身份）。现在可以盘问这些人中的若干个，可以知道被盘问者及他知晓的所有人的身份，但需要保证不能盘问到杀手。现在你知道每个人知晓其他人身份的情况（即已知所有的有向边），求查出杀手是谁且保证不盘问到杀手的最大概率。

若盘问了 \(x\) 个人，则概率为：

\[1-\frac{x}{n} \]

即排除这 \(x\) 个人中存在杀手的概率。

那么最大化概率，等价于最小化被盘问者的数量。

对于所有知晓关系构成的有向图中的某个强连通分量，显然只要盘问其中的任意一个人，那么整个强连通分量内的所有人的身份都会知晓。于是我们对原图进行缩点后，对于形成的 DAG，只需要盘问每个入度为 \(0\) 的结点中的某一个人，就可以知晓所有人的身份。那么答案理应是缩点后入度为 \(0\) 的点的数量，然而，这并不是我们想象得这么简单。

存在一种比较刁钻的情况：若某个强连通分量内只有 \(1\) 个人，且该点孤立（下方无出边），那么在盘问完其他所有强连通分量并知晓其他 \(n-1\) 个人的身份后，这个人就无需再继续盘问了。

所以，我们需要额外考虑缩点后的 DAG 中是否存在强连通分量大小为 \(1\) 的孤点。

还有一种刁钻的情况：若某个强连通分量 \(u\) 内只有 \(1\) 个人，下方存在出边，但是所有出边对应的强连通分量的身份可以被某一其他源头知晓，那么这个强连通分量 \(u\) 内的人也无需盘问。

至此，我们只需要检查是否存在这两种刁钻的情况中的某一种，便可确定是否可以少盘问一个人，进而得到最终的答案。

还有一点需要注意：我们都清楚，SCC缩点后的图中可能会存在重边。对于本题，是需要去除重边的，以避免对每个点的入度判断产生影响，便于我们对第二种刁钻情况的分析：只需要确定该点对应所有出边的点的入度是否均 \(>1\) 即可。

具体实现见 code。

code

割边，边双连通分量 EDCC

应用于无向连通图。所有割边及边双缩点后的点形成一棵树。

tarjan 算法中判定割边的核心：若一条树边的上方点为 \(u\)，下方点为 \(v\)，发现 \(low[v] > dfn[u]\)，则该边为割边。证明可以直接利用 “扎口袋” 原理，得出 \(v\) 没有任何一条回边可以触及到 \(u\) 所在的连通块（最远只能触及到 \(u\) 的下方），因此 \((u, v)\) 成为了连接 \(u,v\) 所在连通块的唯一一条边，是割边。

tarjan 算法与 SCC缩点一致，low 数组的定义不变，边的类型仍分为树边，回边和弃边三种。唯一不同的地方在于有向图变成了无向图，我们仍可以看作是有向图。

注意三种边中回边与弃边的定义有略微改变。

回边与弃边一定对应在一条无向边中（可以看作回边与弃边配对），即：从下往上看是回边的无向边，从上往下看是弃边。

树边所在无向边对应的另一条有向边一定会被跳过搜索，因此树边不与任何其他种类的边配对。

注意无向图的 tarjan 算法 dfs 每个结点时，一定要避免继续搜索父节点！！！

//边双连通分量 EDCC
//DCC缩点后形成的无向图是一棵树，SCC缩点形成DAG
//注：不能处理带重边和自环的图。含重边自环的处理函数见下一个
vector<int> G[N];
int dfn[N], low[N], tim;
int stk[N],top;
int cnt_bri,cnt_dcc;
int dcc[N]; //dcc[u]表示点u在第dcc[u]个边双连通分量上
struct Bridge{int u,v;
}bri[M];void Tarjan_dcc(int u, int father){ dfn[u] = low[u] = ++tim;stk[++top] = u;for(auto v : G[u]){if(!dfn[v]){ // (u, v) 为树边Tarjan_dcc(v, u);low[u] = min(low[u], low[v]); if(low[v] > dfn[u]){ // 割边bri[++cnt_bri] = {u, v};}   }else if(v != father){ // 回边和弃边的情况统一处理（弃边相当于不执行，因为一定有 dfn[v] > dfn[u] >= low[u]），但一定要保证避免回到父节点low[u] = min(low[u], dfn[v]);}}if(dfn[u] == low[u]){++cnt_dcc;int x;do{x = stk[top--];dcc[x] = cnt_dcc;} while(x != u);}
}