洛谷题单指南-连通性问题-P2863 [USACO06JAN] The Cow Prom S（有向图的强联通分量）

原题链接：https://www.luogu.com.cn/problem/P2863

题意解读：有向图的强联通分量模版题。

解题思路：

一、强连通性概念

强连通性是图论中描述有向图顶点间关系的重要概念。对于有向图 G=(V,E)：

强连通：如果图中任意两个顶点 u 和 v 之间存在从 u 到 v 的路径，也存在从 v 到 u 的路径，则称该图是强连通的。

强连通分量(Strongly Connected Component, SCC)：有向图的极大强连通子图。即不能再添加任何顶点而保持强连通性的子图。

二、DFS序

要找到有向图的强连通分量，一个关键知识是掌握DFS序。

DFS序是指对图进行深度优先遍历时，节点被访问的顺序，它记录了节点在DFS过程中首次被访问的时间戳。

设dfn[u]表示节点u的dfs序。

三、有向图的边类型

在有向图DFS过程中，有向边u->v有四种类型：

树边（Tree Edge）：DFS遍历使用的边，构成DFS生成树；指向未访问节点的边。
回边（Back Edge）指向祖先节点的边，可能形成环；v是u的祖先。
横叉边（Cross Edge）：指向非祖先且已访问的节点；v已先被访问。
前向边（Forward Edge）：指向后代节点的非树边；v是u的后代但已先被访问。

可以看到，上图{1,2,3} {4} {5}是三个强联通分量，假设DFS到当前连通分量时，首先访问的节点是1，接下来看如何识别出所有的强联通分量。

对于上图的强连通分量，1是起点，其余点都在1后面访问，最终通过黑色的回边回到1，形成环路。

基于这样的特点我们就可以设计识别强连通分量的流程：

设low[u]表示u通过树边以及回边能到达的节点最小序号；
通过在DFS中不断更新节点dfn[]以及low[]，识别出强联通分量的起点；
从这个起点开始递归过程中的所有节点都属于同一个强联通分量。
强联通分量的起点有什么特点，根据上图分析：

DFS到1时：dfn[1] = 1，low[1]初始化为1（假设这个连通分量的dfs序号从1开始），1加入堆栈
DFS到2时：dfn[2] = 2, low[2]初始化为2，2加入堆栈
DFS到3时：dfn[3] = 3，low[3]初始化为3，3加入堆栈
从3到1（通过回边，1在堆栈中说明是回边）：low[3] = dfn[1] = 1
3回溯时：low[2] = low[3] = 1
2回溯时：low[1] = low[2] = 1
1回溯时：判断low[1] == dfn[1]，说明1是一个强联通分量的起点，则可以弹出堆栈中1前面包括1所有的节点，就是一个强联通分量{1,2,3}。
DFS到4时：dfn[4] = 4，low[4]初始化为4，4加入堆栈
DFS到5时，dfn[5] = 5，low[5]初始化为5,5加入堆栈
5回溯时，判断low[5] == dfn[5]，说明5是一个强联通分量的起点，弹出堆栈中5前面的节点，就是一个强联通分量{5}
4回溯时，判断low[4] == dfn[4]，说明4是一个强联通分量的起点，弹出堆栈中4前面的节点，就是一个强联通分量{4}
为什么在回溯时，如果low[u] == dfn[u]，说明u是强联通分量的起点？

当low[u] == dfn[u]时，表示：u不能通过任何路径到达比u更早被发现的节点，u是当前SCC中最早被发现的节点，因此是起点。
u和栈中u上方的节点形成了一个闭合环，这些节点互相可达，且无法到达更早的节点，因此构成一个完整的强连通分量。
为什么只有树边和回边对连通分量产生影响？

因为只有这两种边才会影响low[]值的计算，才能对low[u] == dfn[u]的判断产生影响，而此判断是找到强联通分量起点的关键。
前向边只是树边的捷径，不带来low值的改变。
横叉边指向的是已经确定过SCC的节点，和起点不在一个SCC中。
以上识别强联通分量的方式，就是Tarjan算法的核心所在。

四、Tarjan算法

在众多的Tarjan算法中，强联通分量算法只是其中一种。

1、核心概念

DFS遍历顺序：算法基于DFS，为每个节点维护两个重要值：

dfn[u]：节点u的发现时间(DFS序号)

low[u]：从u出发通过有向边能回溯到的最早(最小dfn)的节点

栈的使用：使用栈stack来跟踪当前搜索路径上的节点，并用vis[u]标记u是否在栈中

强连通分量判定：当发现low[u]==dfn[u]时，栈中从u到栈顶的所有节点构成一个SCC

2、关键步骤

对于每个未被访问的节点u：
初始化：dfn[u] = low[u] = ++timestamp;
将u压入栈，标记vis[u] = true;
遍历u的所有邻接节点v：
如果v未被访问(!dfn[u])：
递归访问v
回溯时更新：low[u] = min(low[u], low[v])
如果v已被访问且在栈中(vis[v])：
更新low[u] = min(low[u], dfn[v])
检查是否发现SCC根节点：
如果low[u] == dfn[u]
弹出栈中节点直到u被弹出，这些节点构成一个SCC
注意：在有向图的深度优先搜索过程中，当遇到一条回边时，需要通过判断目标节点是否在堆栈中来确定这条回边对于强连通分量的影响。如果目标节点在堆栈中，说明存在从当前节点到其祖先节点的路径，那么当前节点及其子树中的节点与祖先节点及其子树中的节点可能属于同一个强连通分量，需要更新当前节点的low值。如果目标节点不在堆栈中，说明这条回边是指向已经处理过的强连通分量中的节点，对于当前正在处理的强连通分量没有影响。

3、代码示例

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;
    for(int i = h[u]; i; i = ne[i])
    {
        int v = e[i];
        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]) //u是连通分量的起点
    {
        cnt++; //当前强联通分量的编号
        while(true)
        {
            int t = stk.top(); stk.pop();
            vis[t] = false;
            scc[t] = cnt;
            sz[cnt]++; //当前强联通分量中点的数量累加
            if(t == u) break;
        }
    }
}

五、缩点**

强连通分量缩点（SCC缩点）是将有向图中的每个强连通分量收缩为一个超级节点的过程，最终得到一个有向无环图（DAG）。

1、核心思想

强连通分量识别：首先找出图中所有的强连通分量

分量收缩：将每个SCC视为一个超级节点

边重构：在缩点后的图中，如果原图中存在从一个SCC到另一个SCC的边，则在对应超级节点间添加边

2、算法实现

用Tarjan算法识别出每个点所属的强联通分量编号之后

枚举所有边u->v，

如果u所在强联通分量与v所在强联通分量不同，

则将u所在强联通分量与v所在强联通分量作为节点，连一条有向边即可。

3、代码示例

for(int i = 1; i <= n; i++)
{
    for(int j = h[i]; j; j = ne[j])
    {
        int u = scc[i], v = scc[e[j]];
        if(u != v)
        {
            //在缩点图中建立一条从u到v的边
        }
    }
}

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 10005, M = 50005;
int h[N], e[M], ne[M], idx; //链式前向星存图
int dfn[N], low[N], timestamp; //节点的dfs时间戳，能追溯到的最小时间戳
stack<int> stk; //堆栈保存连通分量节点
bool vis[N]; //判断是否在堆栈中，用于识别回边
int scc[N], cnt; //每个点所属的强连通分量编号
int sz[N]; //每个连通分量有多少节点
int n, m;

void add(int a, int b)
{
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;
    for(int i = h[u]; i; i = ne[i])
    {
        int v = e[i];
        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]) //u是连通分量的起点
    {
        cnt++; //当前强联通分量的编号
        while(true)
        {
            int t = stk.top(); stk.pop();
            vis[t] = false;
            scc[t] = cnt;
            sz[cnt]++; //当前强联通分量中点的数量累加
            if(t == u) break;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }

    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);

    int ans = 0;
    for(int i = 1; i <= cnt; i++)
        if(sz[i] > 1)
            ans++;

    cout << ans;
    return 0;
}