引子

树上跑一边DFS的代码很简单吧，图上的DFS与其相差无几。区别在于图上的DFS要记录每一个点是否被遍历过，如果已经被遍历过了，则跳过该点继续DFS；此外这个图有可能是个不完全连通，所以要确保每个点都被遍历到。

由此我们就知道一些有用的东西了，比如图中各点的 DFS 序，或者按照 DFS 序建一棵树：DFS生成树。

图片来自OI wiki

如上图，这就是一个在有向图中的一棵DFS生成树的例子。可以看见，在图中除了黑色的构成树的实边以外，还有一些虚边，它们不存在与生成树中，但却在原图中存在。对于这些边，我们可以给它们分别命名：

1. 树边（ Tree Edge ）：如图中黑色边。搜索时找到了一个没有被访问过的节点，则通过的这条边即为树边。以下均称为T边。
2. 返祖边（ Back Edge ）：如图中红色边。也叫回边。搜索时发现一个是其祖先的节点，则通过的这条边即为返祖边。以下均称为B边。
3. 横插边（ Cross Edge ）：如图中蓝色边。搜索时发现一个已访问过的，非其祖先的节点，则通过的这条边即为横插边。以下均称为C边。
4. 前向边（ Forward Edge ）：如图中绿色边。搜索时发现一个已访问过的，是其子树中的节点，则通过的这条边即为前向边。以下均称为F边。

以上，即为DFS生成树的相关概念。讲解它是为了方便以下内容的理解。

概述

如果一个有向图中每一个点都能相互到达，则称该图为强连通图。一个图的极大子图如果是强连通图，则这个子图为该图的一个强连通分量。

在有向图中求强连通分量最经典的算法就是Tarjan算法了。Tarjan算法 的基本思路就是在 DFS 整个图的同时为每个节点保存两个信息：

• $dfn$

其实就是DFS序。

• $low$

从该节点的子树出发，经过一条B边或C边可以到达的DFS序最小的在栈中的DFS序。

用这两个信息，就可以在DFS的同时找环了，而根据强连通分量的定义易知：一个环一定是一个连通分量。

所以为了方便维护这两个信息，我们引入一个栈，对于遍历到的一个点 $u$ ，栈中保存已遍历过的，能通过某条路径到达 $u$ 的节点。以此来将一个强连通分量里的可能点囊括到一起。
并且我们还需要一个 bool 数组来记录一个点是否在栈中。

Tarjan算法的关键就在于 $low$ ，所以在 DFS 的过程中我们主要针对对 $low$ 数组的更新来进行说明。当DFS遍历到一个点 $u$ 时，对于其接下来将要遍历的节点 $v$ 与二者之间的边 $e$ ，分三种情况考虑：

1. 当 $e$ 为B边时，即 $v$ 已经被遍历过且在栈中时。根据 $low$ 的定义，此时应该用 $v$ 的 $dfn$ 更新 $n$ 的 $low$ 。
2. 当 $e$ 为T边时，即 $v$ 未被遍历过时。继续对 $v$ 进行DFS。当 $v$ 的DFS结束时，在回溯过程中用 $v$ 的 $low$ 更新 $n$ 的 $low$ 。因为 $u$ 跟 $v$ 有直接边，$v$ 更新 $low$ 时能够到达的节点 $u$ 肯定也可以。
3. 当 $v$ 被访问过且不在栈中时。说明 $v$ 所在的强连通分量已经被处理完毕，不必对 $v$ 进行操作，跳过即可。

语言无力，多说无用，不如直接上伪代码：

void Tarjan ( int x ) //其实就是DFS
{
    s.push(x); wy[x]=1; //先入栈
    dfn[x]=low[x]=++cnt; //记录DFS序和low数组
    for ( int i=0 ; i<d[x].size() ; i++ )
        if ( !dfn[d[x][i]] ) //当为T边时
        {
            Tarjan(d[x][i]); //继续DFS
            low[x]=min(low[x],low[d[x][i]]); //并且更新low数组
        }
        else if ( wy[d[x][i]] ) //当为B边时
            low[x]=min(low[x],dfn[d[x][i]]); //更新low数组
    if ( dfn[x]==low[x] ) //如果DFS序与low值相等
    {
        tot++; //则这是一个新的强连通分量
        while ( wy[x] ) //不断弹栈
        {
            int t=s.top(); s.pop();
            id[t]=tot; wy[t]=0;
            siz[tot]++; //弹出的每一个都是这个强连通分量中的节点
        }
    }
}

另外，如果一个点的所有子树都遍历完了，判断一下其DFS序与 $low$ 的值的大小，如果发现其DFS序与 $low$ 值相等，说明这个点是一个强连通分量的“根”，于是不断弹栈，直到将这个点也弹出来，这之前弹出的所有点都与其在同一个强连通分量中。

对于其正确性，不妨这样想：对于每一个强连通分量，有且仅有一个节点的DFS序与 $low$ 值相等，且该节点一定是在DFS过程中第一个被遍历到的。因此其DFS序最小，所以更新 $low$ 时不会被其下方的节点所影响。

而栈中在其之上的所有节点就是它能到达的所有节点，这也就说明其能到达的所有节点无法再到达在其之上的任何一个节点，这在代码中表现为 $low$ 值比其大，不可能比其小，因为这样会在DFS过程中使其更新 $low$ 值。以上，证毕。

Tarjan算法将每条边每个节点都遍历了一次，若有 $n$ 个点和 $m$ 条边，则时间复杂度为 $O(n+m)$ 。

那么说了这么多，强连通有什么用呢？想一想，一个强连通分量中的所有点都可以相互到达，那么不计较经过边数的话，如果一个节点可以到达强连通的其中一个点，那么必然也可以到达强连通的其它点。所以我们可以将一整个强连通分量坍缩成一个点，由此对图中每个强连通分量都进行缩点操作，就可以将一个有向图变成DAG（有向无环图）来解决问题了。这就是缩点。

如果原图是连通图，那么缩点之后就会变成一棵树。

例题

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

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

强连通版子题。不妨这么想：每头奶牛视作一个点，爱慕关系为有向边，则我们可以建一个图。而图中每个强连通分量中的每个点都可以相互到达，即相互爱慕，那么我们就可以将其视作一个点。

对每一个强连通分量，记录其中总点数。缩点完成后再遍历一次新的树，找到叶子节点。因为非叶子节点的子节点无法再到达它，即无法被子节点“爱慕”，只有叶子节点可能被所有点到达。

但还需要再考虑一件事，如果有多个叶子节点，那么这些叶子节点一定不可能互相到达，所以一定没有符合条件的奶牛。只有在只有一个叶子节点时，才输出该叶子节点中包含的点数。

以下为代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+9;
int n,m,tot,cnt,dfn[N],low[N],siz[N],id[N];
bool wy[N];
vector <int > d[N],scc[N];
stack <int > s;
void Tarjan ( int x )
{
    s.push(x); wy[x]=1;
    dfn[x]=low[x]=++cnt;
    for ( int i=0 ; i<d[x].size() ; i++ )
        if ( !dfn[d[x][i]] )
        {
            Tarjan(d[x][i]);
            low[x]=min(low[x],low[d[x][i]]);
        }
        else if ( wy[d[x][i]] )
            low[x]=min(low[x],dfn[d[x][i]]);
    if ( dfn[x]==low[x] )
    {
        tot++;
        while ( wy[x] )
        {
            int t=s.top(); s.pop();
            id[t]=tot; wy[t]=0;
            siz[tot]++;
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for ( int i=1 ; i<=m ; i++ )
    {
        int a,b; scanf("%d %d",&a,&b);
        d[a].push_back(b);
    }
    for ( int i=1 ; i<=n ; i++ )
        if ( !dfn[i] ) Tarjan(i);
    for ( int i=1 ; i<=n ; i++ ) //缩点
        for ( int j=0 ; j<d[i].size() ; j++ )
            if ( id[i]!=id[d[i][j]] ) scc[id[i]].push_back(id[d[i][j]]); //建一个新的树
    int ans=0;
    for ( int i=1 ; i<=tot ; i++ ) //再遍历一次新的树
        if ( !scc[i].size() ) //如果是叶子节点
        {
            if ( ans ) { puts("0"); return 0; } //如果已经有叶子节点了，则无法满足
            ans=siz[i]; //否则记录该叶子节点内部点数
        }
    printf("%d\n",ans);
    return 0;
}

时间复杂度约为 $O(n+m)$ 。

• P2194 HXY烧情侣

一个有向连通图中，燃烧每个点都需要一定费用。如果从某点出发能从一条路径回到该点，那么燃烧这条路径上所有点的总费用就等于这个点所需的费用。现在想燃烧所有的点，每个点可以重复经过。

问：最少需要多少费用，并且当费用最少时的方案数是多少？由于方案数可能过大，所以请输出方案数对 $10^9+7$ 取模的结果。

虽然题面让人看得感同身受，但题目还是很简单的。首先求出强连通分量，然后记录下每个强连通分量中的最小值的点的点数，根据乘法原理，将这些数量相乘就是总方案数。别忘了边乘边模。

以下为代码：

#include <bits/stdc++.h>
#define L long long
using namespace std;
const int N=1e5+9;
const int M=1e9+7;
int n,m,tot,cnt,a[N],dfn[N],low[N],siz[N],id[N];
bool wy[N];
vector <int > d[N],scc[N];
stack <int > s;
void Tarjan ( int x )
{
    s.push(x); wy[x]=1;
    dfn[x]=low[x]=++cnt;
    for ( int i=0 ; i<d[x].size() ; i++ )
        if ( !dfn[d[x][i]] )
        {
            Tarjan(d[x][i]);
            low[x]=min(low[x],low[d[x][i]]);
        }
        else if ( wy[d[x][i]] )
            low[x]=min(low[x],dfn[d[x][i]]);
    if ( dfn[x]==low[x] )
    {
        tot++;
        while ( wy[x] )
        {
            int t=s.top(); s.pop();
            id[t]=tot; wy[t]=0;
            siz[tot]++;
            scc[tot].push_back(t); //记录点
        }
    }
}
int main()
{
    scanf("%d",&n);
    for ( int i=1 ; i<=n ; i++ )
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for ( int i=1 ; i<=m ; i++ )
    {
        int a,b; scanf("%d %d",&a,&b);
        d[a].push_back(b);
    }
    for ( int i=1 ; i<=n ; i++ )
        if ( !dfn[i] ) Tarjan(i);
    L sum=0,num=1;
    for ( int i=1 ; i<=tot ; i++ ) //遍历所有的强连通分量
    {
        int Min=INT_MAX,Cnt=1;
        for ( int j=0 ; j<siz[i] ; j++ )
            if ( Min>a[scc[i][j]] )
                Min=a[scc[i][j]],Cnt=1;
            else if ( Min==a[scc[i][j]] ) Cnt++;
        sum+=Min; num=(num*Cnt)%M; //边乘边模
    }
    printf("%lld %lld\n",sum,num);
    return 0;
}

• P3275 [SCOI2011]糖果

这题将缩点和最短路结合了，需要在scc上跑最短路。

• P1073 [NOIP2009 提高组] 最优贸易

这两题就当作思考题吧，都是强连通必刷题。

总结

有向图中的强连通分量使得对图的操作有了很大的拓展和提升。能将一个有向图变化成一个DAG的功能使其时常与其它算法结合使用。尤其是在连通图中更是能直接变化成一棵树，导致图论相关的算法都可以被包含在里面。因此，强连通是图论课程中比较重要的一个知识点，各位一定要好好掌握，烂熟于心。

拓展

除Tarjan算法以外，还有几种求强连通分量的算法，如Kosaraju算法（时间复杂度 $O(n+m)$、Garbow 算法等。想了解的可以去OI wiki自行查看。