强连通分量 SCC

zifuneko · 2025-10-18 13:55:54 · 算法·理论

定义

强连通：有向图中，如果两点可以互相到达，那么他们俩强连通。
强连通子图：子图中任意两点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大强连通子图。
若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 弱连通的。

kosaraju 算法

以下是下面所用的变量名及其意义：

变量名	意义
\text{vis}[]	记录点的遍历情况
\text{scc}[]	强连通分量的数量
\text{cnt}[i]	i 号强连通分量的规模
vector \text{ kos}	后序及反序 \text{dfs} 序列
\text{g}1	原图
\text{g}2	边反
\text{in}	缩点后的入度
\text{out}	缩点后的出度
set \text{ edge[]}	缩点后去重的图（可优化）

第一次DFS

正向图中搜索得到包含所有店的后序遍历

// 正向图中得到后序遍历序列
void dfs1(int u)
{
    vis[u] = 1;
    for(auto v : g1[u]) // 正向图
        if(!vis[v]) dfs1(v);
    kos.push_back(u);
}

第二次DFS

将序列反转，依次在反图中进行强连通分量标记

// 把 u 所有能到的未标记点全部标记为同一个强连通分量
void dfs2(int u) 
{
    scc[u] = scc_cnt;
    for(int v : g2[u]) // 反向图
        if(scc[v] == 0) dfs2(v);
}

kosaraju 主体

void kosaraju()
{
    //第一步：遍历正向图所有点，得到后序遍历序列
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    reverse(kos.begin(), kos.end()); // 反转序列

    // 第二步：倒序考虑后序遍历序列，在反图中标记每一个强连通分量
    // scc_cnt：强连通分量的数量，顺带作为编号进行标记
    for(auto x : kos)
        if(scc[x] == 0) ++scc_cnt, dfs2(x);
    // 反图中搜索+标记所属强连通分量编号
}

缩点

缩点后变为 DAG，可以进行更多操作。

int in[MAX], out[MAX];
set<int> edge[MAX];
void get_graph()
{
    for(int u=1; u<=n; u++)
    {
        int x = scc[u];
        scc_num += 1; // 点信息
        for(auto v : g1[u])
        {
            int y = scc[v];
            if(x != y) edge[x].insert(y), in[y] ++, out[x] ++; // 外部边信息
        }
    }
}

正确性证明

强连通的两点，无论先搜后搜，都会被标记为相同值。
非强连通的两点，无论先搜后搜，都会被标记为不同值。
在 B 搜索前，A 是否已被标记？——无论在第一次遍历时 A 先还是 A 后在第二次遍历标记时永远是 A 先开始标记，那么由于是一个反向图，因此 A 是无法标记 B 的，且后续从 B 标记开始标记的时候，A 已经被标记了，因此 A 和 B 一定不在同个强连通分量里面。

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

const int MAX = 1e5+5;
vector<int> g1[MAX], g2[MAX], kos;
int vis[MAX], scc[MAX], n, m, scc_cnt=0;

void dfs1(int u)
{
    vis[u] = 1;
    for(auto v : g1[u])
        if(!vis[v]) dfs1(v);
    kos.push_back(u);
}

void dfs2(int u)
{
    scc[u] = scc_cnt;
    for(int v : g2[u])
        if(scc[v] == 0) dfs2(v);
}

void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    reverse(kos.begin(), kos.end());

    for(auto x : kos)
        if(scc[x] == 0) ++scc_cnt, dfs2(x);
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a, b; cin >> a >> b;
        g1[a].push_back(b);
        g2[b].push_back(a);
    }

    kosaraju();
    int cnt[MAX]; for(int i=1; i<=n; i++) cnt[scc[i]]++;
    int ans = 0;
    for(int i=1; i<=scc_cnt; i++)
        if(cnt[i] > 1) ans++;
    cout << ans;
    return 0;
}

Tarjan 算法

场景：强连通分量、割点、割边、点双、边双、圆方树。

DFS 生成树

有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：

过程

Tarjan 算法基于对图进行深度优先搜索。我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中。

在 Tarjan 算法中为每个结点 u 维护了以下几个变量：

一个结点的子树内结点的 \text{dfn} 都大于该结点的 \text{dfn}。从根开始的一条路径上的 \text{dfn} 严格递增，\text{low} 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 \text{dfn} 与 \text{low} 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 u 和与其相邻的结点 v（v 不是 u 的父节点）考虑 3 种情况：

实现

下面是代码中变量名及其解释：	变量名	释义
全局	<
\text{val[]}	每个结点的点权（权值）。之后 SCC 缩点时会把每个 SCC 内所有点的点权相加。
vector\ \text{edge[]}	原图的邻接表。
vector\ \text{tar\_edge[]}	缩点之后得到的 DAG 图的邻接表。
\text{tarjan()}	<
\text{dfn[]}	DFS 序编号（访问次序）。当 `dfn[u] == 0` 时，表示这个点还没被访问过。
\text{low[]}	`low[u]` 表示：从 u 出发，通过树边和返祖边能到达的最小 \text{dfn} 值。
\text{tar\_index}	全局 DFS 序的计数器。
\text{tar\_stack[]}	Tarjan算法的栈，用来存当前 DFS 搜索路径上的点。栈中元素都是 “已经访问但尚未归属到某个 SCC 的点”。
\text{top}	栈顶指针。
缩点	<
\text{scc\_cnt}	强连通分量的编号计数器。
\text{scc\_id[]}	这个点属于哪个 SCC，在弹栈时赋值。
\text{scc\_val[]}	每个 SCC 的总点权。在弹栈时，把该 SCC 中所有点的权值累加。
\text{scc\_num[]}	每个 SCC 包含多少个结点。
\text{rd[]}	新图的入度（in-degree）
\text{cd[]}	新图的出度（out-degree）

P3387 【模板】缩点

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

const int MAX = 1e6+5;
int n, m, val[MAX], dfn[MAX], low[MAX]; // low: 能到达的最小dfn序
int scc_cnt, tar_index, scc_id[MAX], scc_val[MAX], scc_num[MAX], tar_stack[MAX], top;
vector<int> tar_edge[MAX], edge[MAX];

void tarjan(int u)
{
    low[u] = dfn[u] = ++tar_index;
    tar_stack[++top] = u; // 入栈

    for(auto v : edge[u])
        //树边：新点没有设置 dfn
        if(dfn[v] == 0) tarjan(v), low[u] = min(low[u], low[v]);
        // 非树边没标记：统一的操作方法
        else if(scc_id[v] == 0) low[u] = min(low[u], low[v]);

    /*
    本质上就是在 DFS 中维护 low 值：
     - 树边：继续搜索，然后用儿子的 low 维护。 
     - 返祖边：用祖先的 dfn 维护。
     - 前向边：用子孙的 dfn 维护。
     - 横叉边：如果没有被标记，用该点的 dfn 维护。
    */

    if(dfn[u] == low[u]) // 找到一个强连通分量的顶点。
    {
        ++scc_cnt; // 强连通分量编号
        int x; do
        {
            x = tar_stack[top--]; // 弹出的点
            scc_id[x] = scc_cnt; // 编号
            scc_val[scc_cnt] += val[x];
        }
        while(u != x); // 如果弹出的点不是 u 就继续
    }
}

// tarjan 主体
void target()
{
    for(int i=1; i<=n; i++)
        if(scc_id[i] == 0) tarjan(i);
}

int rd[MAX], cd[MAX];
void get_graph()
{
    // 统计每一个强连通分量的结点数量。
    for(int i=1; i<=n; i++) scc_num[scc_id[i]]++;
    //统计每一个强连通分量的入度和出度并重新构图
    for(int u=1; u<=n; u++)
        for(auto v : edge[u])
            if(scc_id[u] != scc_id[v])
                tar_edge[scc_id[u]].push_back(scc_id[v]),
                rd[scc_id[v]] ++, cd[scc_id[u]] ++;
}

// 状态：dp[i] 表示所有到 i 终止的路径中，最大点权和
// 转移：dp[u] + val[v] --max-> dp[v]
// 初始：dp[i] = val[i]
int dp[MAX];
void kahn()
{
    queue<int> sk;
    for(int i=1; i<=scc_cnt; i++)
    {
        dp[i] = scc_val[i];
        if(rd[i] == 0) sk.push(i);
    }
    while(!sk.empty())
    {
        int u = sk.front();
        sk.pop();

        for(auto v : tar_edge[u])
        {
            dp[v] = max(dp[v], dp[u] + scc_val[v]);
            if(--rd[v] == 0) sk.push(v);
        }
    }
}

void tar_clear()
{
    tar_index = scc_cnt = 0;
    for(int i=1; i<=n; ++i) 
    {
        scc_id[i] = scc_num[i] = low[i] = dfn[i] = 0;
        tar_edge[i].clear();
    }
}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1; i<=m; i++)
    {
        int u, v; cin >> u >> v;
        edge[u].push_back(v);
    }
    target();
    get_graph();
    kahn();
    int ans=0; for(int i=1; i<=scc_cnt; i++) ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}

割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

红色的边就是割边。

求解

把无向图看成有向图，发现有三种情况（记 u 的子节点为 \textit{son}）：

模版

【模板】割边

题目描述

给定一个 n 个点 m 条边的无向图，求割边数量。

输入格式

第一行两个整数 n,\ m。

接下来 m 行，每行两个整数 u,v，表示一条连接 u 和 v 的边。

输出格式

共一行，输出值为割边数量。

in #1

out #1

说明/提示

对于 100\% 的数据，1\leq n\leq5\times10^4,\ 1\leq m\leq 3\times10^5。

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

const int MAX = 3e5+5;
int n, m, low[MAX], dfn[MAX], tar_index, is_cnt[MAX];
struct Edge {int v, id;};
vector<Edge> edge[MAX];

// e_id 表示来边的编号，防止回搜
void tarjan(int u, int e_id)
{
    dfn[u] = low[u] = ++tar_index;
    for(auto [v, id] : edge[u])
        if(dfn[v] == 0)
        {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            // 对于每条边，跑完后判断
            if(low[v] > dfn[u]) is_cnt[id] = true;
        }
        else if(e_id != id) low[u] = min(low[u], dfn[v]);
}

void target()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i]) tarjan(i, 0);
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back({v, i});
        edge[v].push_back({u, i});
    }
    target();
    int ans=0;
    for(int i=1; i<=m; i++)
        if(is_cnt[i]) ans++;
    cout << ans;
    return 0;
}

割点

P3388 【模板】割点（割顶）

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

const int MAX = 3e5+5;
int n, m, low[MAX], dfn[MAX], tar_index, is_cut[MAX], cut_num=0;
vector<int> edge[MAX];

void tarjan(int u, int root)
{
    dfn[u] = low[u] = ++tar_index;

    int son = 0;
    for(auto v : edge[u])
        if(dfn[v] == 0)
        {
            son++;
            tarjan(v, root);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u] && u != root)
                cut_num += 1 - is_cut[u],
                is_cut[u] = true;
        }
        else low[u] = min(low[u], dfn[v]);
    if(son >= 2 && u == root) cut_num += 1 - is_cut[u], is_cut[u] = true;
}

void target()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i]) tarjan(i, i);
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    target();
    cout << cut_num << endl;
    for(int i=1; i<=m; i++)
        if(is_cut[i]) cout << i << ' ';

    return 0;
}

边双点双

在一张连通的无向图中，对于两个点 𝑢 和 𝑣，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 𝑢 和 𝑣 边双连通。

在一张连通的无向图中，对于两个点 𝑢 和 𝑣，如果无论删去哪个点（只能删去一个，且不能删 𝑢 和 𝑣 自己）都不能使它们不连通，我们就说 𝑢 和 𝑣 点双连通。

边双连通具有传递性，即，若 𝑥, 𝑦 边双连通，𝑦, 𝑧 边双连通，则 𝑥, 𝑧 边双连通。

点双连通 不具有 传递性。

对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量。
对于一个无向图中的极大点双连通的子图，我们称这个子图为一个点双连通分量。

Tarjan 强连通 + “回边处理” \to 强连通分量 \to 边双连通分量

无向图 \to 有向图 + 禁止回边

注意只能判断“回边”不能判断“回点”。因为可能会出现多重边的问题。

P8436 【模板】边双连通分量

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

const int MAX = 1e6+5;
int n, m, dfn[MAX], low[MAX]; // low: 能到达的最小dfn序
int ebcc_cnt, tar_index, bcc_id[MAX], tar_stack[MAX], top;
struct Node {int v, id;};
vector<Node> tar_edge[MAX], edge[MAX];
vector<int> bcc[MAX];

void tarjan(int u, int e_id)
{
    low[u] = dfn[u] = ++tar_index;
    tar_stack[++top] = u; // 入栈

    for(auto [v, id] : edge[u])
        if(dfn[v] == 0) tarjan(v, id), low[u] = min(low[u], low[v]);
        else if(id != e_id) low[u] = min(low[u], dfn[v]);

    if(dfn[u] == low[u])
    {
        ++ebcc_cnt;
        int x; do { x = tar_stack[top--]; bcc_id[x] = ebcc_cnt; }
        while(u != x);
    }
}

// tarjan 主体
void target() { for(int i=1; i<=n; i++) if(bcc_id[i] == 0) tarjan(i, i); }

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int u, v; cin >> u >> v;
        edge[u].push_back({v, i});
        edge[v].push_back({u, i});
    }
    target();
    cout << ebcc_cnt <<endl;
    for(int i=1; i<=n; i++)
        bcc[bcc_id[i]].push_back(i);
    for(int i=1; i<=ebcc_cnt; i++)
    {
        cout << bcc[i].size() << ' ';
        for(auto t : bcc[i]) cout << t << ' ';
        cout << endl;
    }

    return 0;
}

P8435 【模板】点双连通分量

发现点双会重复计入割点，我们不能再弹出 u，而需要保留 u 并加入 u.

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

const int MAX = 2e6+5;
int n, m, dfn[MAX], low[MAX];
int vbcc_cnt, tar_index, bcc_id[MAX], tar_stack[MAX], top;
struct Node {int v, id;};
vector<Node> edge[MAX];
vector<int> bcc[MAX], ans[MAX];

void tarjan(int u, int e_id)
{
    low[u] = dfn[u] = ++tar_index;
    tar_stack[++top] = u;

    int son = 0;
    for(auto [v,id] : edge[u]) {
        if(dfn[v] == 0) 
        {
            son++;
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) // 起点 + 割点
            {
                ++vbcc_cnt;
                int x;
                do {x = tar_stack[top--]; ans[vbcc_cnt].push_back(x);} while(v != x); // 保留 u
                ans[vbcc_cnt].push_back(u); // 加入 u
            }
        }
        else if(id != e_id) low[u] = min(low[u], dfn[v]);
    }
    if(e_id == 0 && son == 0) ans[++vbcc_cnt].push_back(u); // 特殊的特判：孤立点
}

// tarjan 主体
void target() { for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i, 0); }

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int u, v; cin >> u >> v;
        edge[u].push_back({v, i});
        edge[v].push_back({u, i});
    }
    target();
    cout << vbcc_cnt <<endl;
    for(int i=1; i<=vbcc_cnt; i++)
    {
        cout << ans[i].size() << ' ';
        for(auto t : ans[i]) cout << t << ' ';
        cout << endl;
    }
    return 0;
}