本文理论内容较多，建议读者配合画图理解。

有向图

DFS生成树

在讨论后续内容前，我们先了解DFS生成树，这是学习Tarjan算法家族的基础。

以下DFS生成树基于有向图，无向图部分将在后面介绍。

DFS生成树包含四种类型的边：树边、前向边、返祖边（也称反向边）和横叉边。下图展示了这些类型：

在这棵DFS生成树中，黑色边为树边，是在DFS遍历过程中获得的；红色边为返祖边，从子节点指向父节点或祖先节点；蓝色边为横叉边，在搜索遇到子树中的节点时形成；粉色边为前向边，在搜索遇到子树中的节点时形成。

强连通分量

强连通分量具有两个重要特性：强连通性和极大性。强连通性意味着分量内的任意两个节点都可以互相到达（直接或间接）。极大性表示无法再加入任何其他节点而不破坏强连通性。

强连通分量通常在有向图中讨论，在无向图中则退化为连通块。

为了更好地理解强连通分量，我们来看下图示例：

此图中存在两个强连通分量：{1,2,3}和{1,5,6}。由此可见，一个节点可以属于多个不同的强连通分量。

Tarjan算法

求强连通分量的方法有多种，这里主要介绍最常见的Tarjan算法。

在讲解Tarjan算法前，我们定义以下概念：

• dfn[u]：节点u在DFS遍历中的顺序编号
• low[u]：节点u经过若干条树边和最多一条返祖边能到达的dfn值最小的节点

在一个强连通分量中，有且仅有一个节点的dfn值等于low值，这个节点是该分量中最早被DFS遍历到的节点（dfn值最小），我们称之为该强连通分量的祖先。这个性质在Tarjan算法中非常重要。

low值可以在DFS过程中计算。对于边(u,v)：

• 如果v未被访问，则先递归访问v，然后用low[v]更新low[u]，因为u和v相连，v能到达的点u也能到达
• 如果v已被访问且v能到达u（即u在栈中），则用dfn[v]更新low[u]
• 如果v已被访问但不能到达u，则不做处理

判断v能否到达u可以通过维护一个栈来实现，每次DFS将当前节点压入栈，判断u是否在栈中即可。

计算完每个节点的low值后，如何求强连通分量呢？这里用到前面提到的性质：在一个强连通分量中，仅有一个节点的dfn值等于low值（即祖先节点）。因此，在回溯时，若发现节点的dfn值等于low值，则该节点是一个强连通分量的祖先，栈中该节点以上的所有节点都属于该强连通分量，将这些节点出栈并统计结果。

强连通分量常与缩点技术结合使用。由于强连通分量的极大性，缩点后得到的有向无环图(DAG)可以进行动态规划或最短路径计算。

以下是Tarjan算法的实现示例：

有向图中求强连通分量的Tarjan算法``` void Tarjan(int pos) { dfn[pos] = low[pos] = ++timestamp; inStack[pos] = true; stack.push(pos);

for(int i=0; i<graph[pos].size(); i++)
{
    int neighbor = graph[pos][i];
    if(!dfn[neighbor])
    {
        Tarjan(neighbor);
        low[pos] = min(low[pos], low[neighbor]);
    }
    else if(inStack[neighbor])
    {
        low[pos] = min(low[pos], dfn[neighbor]);
    }
}

if(dfn[pos] == low[pos])
{
    componentId++;
    while(stack.top() != pos)
    {
        componentSize[componentId]++;
        vertexToComponent[stack.top()] = componentId;
        inStack[stack.top()] = false;
        stack.pop();
    }
    stack.pop();
    componentSize[componentId]++;
    vertexToComponent[pos] = componentId;
    inStack[pos] = false;
    newComponentGraph[componentId][componentId] = 1;
}

}

### 练习题

#### A

模板题：Luogu P3387 [模板]缩点

#### 题目描述

> 给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
> **允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次**。

#### 解析

首先，题目允许多次经过边或点，但只计算一次点权，这一点非常重要。

考虑重复走更优的情况：**环**。如果存在环，我们可以走完整个环，将环上所有点的权值都计入，显然更优。其他情况下多次经过无意义。

如果没有环，直接动态规划即可；如果有环，我们可以通过**Tarjan缩点**将图转化为有向无环图(DAG)，然后进行动态规划或记忆化搜索。

本题主要考察代码实现能力。

#### 代码实现

Tarjan求强连通分量模板```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#define MAXN 10010
using namespace std;

int n, m;
int vertexValue[MAXN], componentSum[MAXN];
vector<int> graph[MAXN];
vector<int> newGraph[MAXN];
int dfn[MAXN], low[MAXN], vertexToComponent[MAXN];
int timestamp = 0;
bool inStack[MAXN];
stack<int> nodeStack;
int componentCount = 0;
int inDegree[MAXN];
int maxValue = -1;
int dp[MAXN];

void Tarjan(int node)
{
    dfn[node] = low[node] = ++timestamp;
    inStack[node] = true;
    nodeStack.push(node);
    
    for(int i=0; i<graph[node].size(); i++)
    {
        int neighbor = graph[node][i];
        if(!dfn[neighbor])
        {
            Tarjan(neighbor);
            low[node] = min(low[node], low[neighbor]);
        }
        else if(inStack[neighbor])
        {
            low[node] = min(low[node], dfn[neighbor]);
        }
    }
    
    if(dfn[node] == low[node])
    {
        componentCount++;
        while(nodeStack.top() != node)
        {
            componentSum[componentCount] += vertexValue[nodeStack.top()];
            vertexToComponent[nodeStack.top()] = componentCount;
            inStack[nodeStack.top()] = false;
            nodeStack.pop();
        }
        nodeStack.pop();
        componentSum[componentCount] += vertexValue[node];
        vertexToComponent[node] = componentCount;
        inStack[node] = false;
    }
}

int topologicalSort(int node)
{
    if(dp[node]) return dp[node];
    
    int maxComponentValue = 0;
    for(int i=0; i<newGraph[node].size(); i++)
    {
        maxComponentValue = max(maxComponentValue, dp[newGraph[node][i]]);
    }
    
    dp[node] = maxComponentValue + componentSum[node];
    maxValue = max(maxValue, dp[node]);
    return dp[node];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> vertexValue[i];
    
    for(int i=1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    
    for(int i=1; i<=n; i++) 
    {
        if(!dfn[i]) Tarjan(i);
    }
    
    for(int i=1; i<=n; i++)
    {
       for(int j=0; j<graph[i].size(); j++)
       {
            if(vertexToComponent[i] != vertexToComponent[graph[i][j]]) 
            {
                bool canAdd = true;
                for(int k=0; k<newGraph[vertexToComponent[i]].size(); k++)
                {
                    if(newGraph[vertexToComponent[i]][k] == vertexToComponent[graph[i][j]]) 
                    {
                        canAdd = false;
                        break;
                    }
                }
                if(canAdd)
                {
                    newGraph[vertexToComponent[i]].push_back(vertexToComponent[graph[i][j]]);
                    inDegree[vertexToComponent[graph[i][j]]] ++;
                }
            }
       }
    }
    
    for(int i=1; i<=componentCount; i++)
    {
        if(!dp[i]) 
        {
            topologicalSort(i);
        }
    }
    
    cout << maxValue << endl;
    return 0;
}

以上实现较为复杂，当然有更简洁的实现方式，仅供参考。

B

参见链接

以上内容均基于有向图，下文我们将探讨无向图。

无向图

DFS生成树

对于连通无向图G=(V,E)，通过DFS算法得到的一棵生成树称为该连通无向图的DFS树。

与有向图类似，我们将生成树上的边称为树边，非生成树上的边统称为环边。

在无向图中，不再有"返祖边、横插边、前向边"等分类，无向图中只存在树边和环边。

下文令dfn[x]表示x在DFS遍历中的顺序编号。

low[x]表示x及其子树通过一条环边能回到的dfn值最小的节点。

这些定义与有向图中的定义类似。

割点与割边

割点：如果删除无向图中的某个点u（及其连接的边）后，图变为非连通图，则称点u为割点。

割边：如果删除无向图中的一条边后，图变为非连通图，则称该边为割边。

接下来我们考虑边(u,v)何时为割边。

定理：

• 若(x,y)是环边，则该边一定不是割边。
• 若(x,y)是树边，设在DFS树中x是y的父亲，则该边是割边当且仅当low[y] > dfn[x]。

对于定理1，若(x,y)为环边，删除后仍可通过树边保持连通。

对于定理2，当low[y] > dfn[x]时，意味着y无法跳过x向上连通，即y及其子树都无法到达x以上的节点，因此该边为割边。

类似地，我们可以得到点x是割点的条件：

• 若点x是根节点，且它有两个或更多儿子，则为割点。
• 若点x非根节点，则x为割点当且仅当存在一个儿子y使得low[y] > dfn[x]。

点双连通分量与边双连通分量

在割点和割边的基础上，我们引入点双连通分量和边双连通分量的概念。

• 点双连通图：若一个无向连通图不存在割点，则称为点双连通图。
• 边双连通图：若一个无向连通图不存在割边，则称为边双连通图。

"分量"意味着极大性，即点双连通分量和边双连通分量分别是极大的点双连通图/边双连通图。

常见的，边双连通图的等价定义为图中任意两点间不存在边不相交的路径，点双连通图等价定义为图中任意两点间存在至少两条点不相交的路径。

通过上述定义，不难得出：割边是分割两个边双连通分量的边，但割点是不同点双之间的交集点。

即每条边最多属于一个边双，但每个点可以属于多个点双。（因此边双缩点后可转化为树，但点双缩点后转化为圆方树。）

（引用一张信友队讲义截图。）

应用Tarjan算法求解点双/边双时，我们回顾以下结论：

割边是分割两个边双连通分量的边，割点是不同点双之间的交集点。

求解边双时，我们使用一个栈，遇到割边时弹栈，取出边双中的所有点。

求解点双同理，遇到割点时取出点双中的所有点。

练习

CF1000E We need more booses

题目描述

给定一个n个点m条边的无向图，保证图连通。找到两个点s,t，使得s到t必须经过的边最多（一条边无论走哪条路线都经过它，这条边就是必须经过的边），2≤n≤3×10^5,1≤m≤3×10^5

解析

"必须经过"即为割边。因此，我们边双连通分量缩点后求直径即可。

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

题目描述

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

解析

有趣。

注意到"喜欢"关系满足传递性且为单向，考虑点双连通分量缩点。缩点后，每个点集内的点都互相喜欢。

缩点后，图会变成一个树。由于点双连通分量的极大性，此时的树不满足互相喜欢的性质。因此，若点集A喜欢B，则点集B不喜欢A。

考虑满足何条件的集合是被所有点喜欢的。

显然，出度为0的点符合条件。因为若点集A出度不为0，即它喜欢别的点，那么它就不可能被所有点喜欢。

还有一个问题：若有两个或以上的点出度为0呢？那就无解。

P2860 [USACO06JAN] Redundant Paths G

题目描述

给定无向图G=(V,E)，求至少添加多少条边，使得无向图G边双连通。

解析

在图上考虑较复杂，我们先考虑树上的操作。

我们重定义"叶子"为度数为1的点。该定义在Tarjan算法中很常见。

事实上，边双连通分量满足性质：每个点的度数至少为2。这很显然，若一个点的度数只为1，则删除该边后，该点不连通，即该边是割边。

因此，我们统计树上有多少个点的度数为1，然后两两连边即可。

如何连边是最优的呢？

我们将所有的叶子从左到右编号，最大的连最小的，以此类推，这样操作完后整张图是连通的。

设叶子数量为m，则至少需要连⌈m/2⌉条边（多出来的叶子随便连一个即可）。

CF487E Tourists

题目描述

有一个无向图G=(V,E)，请支持如下两种操作。

• C a w 表示点a点权修改为w
• A a b 表示查询从a走到b，所有路径中的最小值最小。

需要注意，一个路径不得重复经过一个点。

解析

路径不可以重复经过一个点，考虑点双缩点。

点双缩点后变成了圆方树。圆方树上方点的儿子都可以互相到达且不会重复经过一个点。

因此，对于每个方点，我们维护它的儿子权值最小值，路径上的每个圆点是割点，我们一定要算贡献。这个可以用树链剖分维护。

但这样有个弊端，对于每个圆点更新，我们可能要更新好几个方点的贡献，因为每个点可能属于多个点双。

事实上，我们只需要更新每个圆点父亲方点的权值即可。因为路径上的权值我们都算过贡献了，不必重复操作。

这样复杂度就是对的。

笔者还没写。太菜了。