Tarjan算法在程序设计竞赛中的应用探析

郭涵涛　毛玉萃

关键词：Tarjan；程序类竞赛；实例

中图分类号：TP311.52 文献标识码：A

文章编号：1009-3044（2023）12-0029-05

1 Tarjan 算法简述[1]

Tarjan 算法是基于深度优先搜索的算法，由著名计算机科学家Robert Tarjan发明，用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥，进一步地可以求解无向图的连通分量；也可以求解有向图的强连通分量、必经点与必经边；该算法是图论中非常实用且常用的算法之一，能解决强连通分量，双连通分量，割点和桥，以及求最近公共祖先（LCA） 等问题。

1.1 Tarjan 问题中的概念介绍

割点：如果一个节点X和所有与X关联的边从图中删除后，图会被分割成两个或两个以上不相连的子图，那么这个分割点就叫作X。

割边：如果把图中的边e去掉后，图就会被分割成两个不相连的子图，那么这条边或者叫切边或者叫割边。

时间戳：时间戳是用来标记图中每个节点在进行深度优先搜索时被访问的时间顺序，用dfn[x]来表示。

搜索树：在无向图中，从某一个节点x 出发进行深度优先搜索，每一个节点只访问一次，所有被访问过的节点与边构成一棵树，称之为“无向连通图的搜索树”。

追溯值：追溯值用来表示从当前节点x 作为搜索树的根节点出发，能够访问到的所有节点中，时间戳最小的值，用low[x]来表示。所有节点包含：

1） 以x为根的搜索树的所有节点。

2） 通过一条非搜索树上的边，能够到达搜索树的所有节点。

1.2 Tarjan 算法的原理[1]

Tarjan 算法是一种利用深度优先搜索实现的图算法，它能够将图中的节点按照强连通分量进行划分，并将同一强连通分量中的节点放在一起。在搜索过程中，将未处理的节点加入一个栈中，并在回溯的过程中检查栈顶到栈中的节点是否构成了一个强连通分量。因此，每个强连通分量对应于深度优先搜索树中的一棵子树。

算法：

1） 当首次搜索到点u时dfn[u]=low[u]=time;

2） 每当搜索到一个点，把该点压入栈顶;

3） 当u和v有边相连时：

当节点v不在栈中时（即遇到树枝边），执行dfs（v） 操作，并将low[u]的值更新为min{low（u）， low（v）}；当节点v在栈中时（即遇到前向边或后向边），将low[u]的值更新为min{low[u]， dfn[v]}。

4） 当一个节点u的dfn值等于其low值时，意味着它所在的强连通分量已经被完全探索并且已经被压入栈中。因此，可以将该节点及其在栈中之前的所有节点弹出栈，这样弹出的节点构成的集合就是一个强连通分量。

5） 继续搜索，直到图被遍历完毕。Tarjan算法的时间复杂度为O（n+m），因为在该算法中，每个节点仅被遍历一次，每条边也仅被遍历一次。

1.3 Tarjan 算法的竞赛意义

各类程序设计竞赛里考察Tarjan的题目相比于其他算法题目并不是特别常见，但研究此类算法却是小组成员学习其他图论算法的必备条件之一。程序设计竞赛对计算机相关专业的学生来说有着很大的帮助，考验着学生的耐心、专注度、逻辑水平等。

1.4 Tarjan 算法的C++代码

Tarjan算法的用C++实现的代码如图1所示。

2 Tarjan 算法在程序设计竞赛中几种典型运用

2.1 割点（割顶）问题[2]

题目：给定一个包含n 个节点和m 条无向边的图，需要找出使图不连通的最少节点集合，这个集合中的每个节点都是图的割点。

输入：第一行输入两个正整数n，m。

输入m 条边，每条边用两个正整数x 和y 表示，表示节点x 和节点y 之间有一条无向边。输出：第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

样例输入：6 7

1 2

1 3

1 4

2 5

3 5

4 5

5 6 样例输出：1

5

分析：标准Tarjan割点题，按照定义去求即可，用C++实现的代码如图2所示。

2.2 The Cow Prom S 问题[3]

题目：有一个n 个点，m 条边的有向图，请求出这个图点数大于1 的强联通分量个数。

输入：第一行为两个整数n 和m。

從第二行到第m+1 行，每行给出两个整数a 和b，表示有一条从节点a 指向节点b 的有向边。

输出：仅一行，表示点数大于1 的强联通分量个数。

样例输入：5 4

2 4

3 5

1 2

4 1

样例输出：1

分析：要解决Tarjan 强连通分量问题，需要使用Tarjan 算法对图进行计算，并统计强连通分量的数量。其主要部分代码如图3所示。

2.3 受欢迎的牛G 问题[4]

题目：每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。每头奶牛总是喜欢自己的，奶牛之间的“喜欢”是可以传递的——如果A 喜欢B，B 喜欢C，那么A 也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入：第一行：两个用空格分开的整数：N 和M。

接下来M 行：每行两个用空格分开的整数：A 和B，表示A 喜欢B。

输出：一行单独一个整数，表示明星奶牛的数量。

样例输入：3 3

1 2

2 1

2 3

样例输出：1

分析：利用Tarjan 算法对图进行强连通分量的计算并缩点后，可以得到一张有向无环图（DAG），其中每个强连通分量被缩成一个点。在这个DAG 中，最受欢迎的奶牛可以被定义为出度为0的点，也就是那些没有任何后继节点的点。这个强连通分量的奶牛数量极为最受欢迎的奶牛数量，同时，如果有两个及两个以上的强连通分量则没有最受欢迎的奶牛。因为这几个强连通分量的奶牛无法相互传递“喜欢”，无法被所有奶牛喜欢。

其主要代码如图4所示。

2.4 缩点问题[5]

题目：给定一个n 个点m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入：第一行两个正整数n，m。

第二行n 个整数，其中第i 个数ai 表示点i 的点权。

第三至m+2 行，每行两个整数u，v，表示一条u→v 的有向边。

输出：共一行，最大的点权之和。

样例输入：2 2

1 1

1 2

2 1 样例输出：2

解析：由题意可知，需要找到一条点权和最大的路径，且可以重复走。这样第一时间就会考虑到出现环的情况，在题目要求权值最大的情况下，有环肯定需要把环上的点全走一遍。这时候就会用到缩点的技巧。如果不使用缩点，很多算法都无法兼容。使用完缩点之后就可以正常处理。

因为是有向图，可以采用拓扑排序+dp来进行顺推答案，维护到达点的最大权值和。其实现的主要部分代码如图5所示。

2.5 Line Graph Matching（2021ICPC 沈阳站）问题[6]

题目：在图论这门数学学科中，一个简单的无向加权图G 的线图是另一个简单的有向加权图L（G）。线图L（G）是一种由图G 转换而来的图形，它的构造方法是：将图G 中的每个顶点用一条线段表示，线段的长度等于该顶点的度数；然后在L（G） 中，若图G 中有两条边e1 和e2 共享一个顶点v，则在L（G） 中会用一个点来连接顶点e1 和顶点e2。因此，L（G） 表示的是图G 中每两条边之间的邻接关系，这种关系可以通过连接L（G） 中的点来表示。

具体来说，对于没有环或多条边的无向加权图G，其线图L（G）是一个无向的加权图，满足以下条件：

L（G）的每个顶点表示G的一条边；

如果在图G中，两个顶点之间的边的权重等于它们对应边的权重之和，并且这两个顶点对应的边共享一个公共点，那么这两个顶点就是相邻的。

简单无向加权图中的最大加权匹配被定义为一组边，其中没有两条边共享一个公共顶点，并且该集合中的边的权重之和被最大化。

给定一个简单的无向加权连通图G，你的任务是找到L（G）的最大加权匹配中的边的权重之和。

输入：第一行包含两个整数n和m，表示顶点数和给定图G中的边数。

然后沿着m条线，其中第i条线包含三个整数u，u 和w，表明图中的第i条边是w的权重，并连接第u个顶点和第v个顶点。保证了图G是连通的，并且不包含循环和多条边。

输出：输出包含单个整数的行，表示L（G）的最大加权匹配中的边的权重之和。

样例输入：5 6

1 2 1

1 3 2

1 4 3

4 3 4

4 5 5

2 5 6

样例输出：21

解析：该题有两种情况，一种情况为边的数量为偶数，由深度优先搜索树可以推出，如果一个节点的子树有一条边未匹配，则使用父节点的边进行配对，如果子树完美配对，则继续往上递归。所以，偶数条边一定可以把所有边进行完美配对。

另一种情况为边的数量为奇数，可以按照上一种情况转换，相当于偶数条边去掉了一条边。

删边之后会有两种情况，一种为分成两个联通块（删的边为割边），另一种为偶数条边的单个联通块（删的边为非割边）。

前者又分为两个奇数条边联通块，和两个偶数条边联通块。前者因为会加大损耗，且可以转换成另外两种情况。

最后结果为取两种情况的最小值（删掉损失最小的边），剩下的即为最大的权重之和。其实现的主要部分代码如图6所示。

3 Tarjan 算法在其他算法中的运用

拓扑排序：Tarjan算法可以用来对有向无环图进行拓扑排序。

二分图检测：Tarjan算法可以用于检测一个无向图是否为二分图。

最小生成树：Tarjan算法可以用于Kruskal算法中的最小生成树算法，以找到图中的最小生成树。

有向无环图的最长路径：通过对有向无环图进行拓扑排序，可以使用Tarjan算法来找到有向无环图的最长路径。

网络流算法：Tarjan算法可以用于网络流算法中，例如在最大流算法中，它可以用来找到残量图中的增广路径。

总之，Tarjan算法是一个非常有用的算法，可以应用于多种图论的算法中，并且在实践中得到广泛的应用。

4 Tarjan 算法在工程上的运用

1） 编译器中的语法分析：在编译器中，Tarjan 算法被应用于生成语法分析器。语法分析器的任务是将源代码转化为一个抽象语法树，然后进行语义分析和生成代码。Tarjan算法可以在语法分析器中用于检测循环依赖和死锁等问题。

2） 数据库中的事务管理：在数据库管理系统中，Tarjan算法可以用于事务管理，特别是在分布式数据库中。在这种情况下，Tarjan算法可以用于检测数据库中的死锁，以确保事务的正确执行。

3） 图形编辑器中的拓扑排序：在图形编辑器中，Tarjan算法可以用于执行拓扑排序，以便在处理有向无环图时能够按照正确的顺序处理图形元素。

4） 软件工程中的模块依赖分析：在软件工程中，Tarjan算法可以用于模块依赖分析。模块依赖分析可以帮助开发人员识别软件模块之间的依赖关系，以便更好地组织和管理代码库。

5） 网络协议中的路由算法：在网络协议中，Tarjan 算法可以用于路由算法，以帮助网络节点找到最佳的路由路径。例如，在因特网中，Tarjan算法可以用于实现BGP（Border Gateway Protocol） 协议，以帮助互联网服务提供商找到最佳的路由路径。

总的来说，Tarjan算法是一种非常通用的算法，可以应用于多个领域和场景中。

5 总结

Tarjan算法在解决强连通分量问题方面具有重要的地位，它在解决强连通分量问题方面具有重要的地位，还可以应用到许多其他的图算法中。它不仅在理论上有著优秀的性能表现，而且在实际应用中也得到了广泛的使用和验证。