有向图的强连通分量

mango09 · 2021-08-02 16:30:04 · 题解

B3609 [图论与代数结构 701] 强连通分量

一些概念：

若一张有向图中任意两个节点 x,y，存在 x 到 y 的路径和 y 到 x 的路径，则称其为强连通图；
有向图的极大强连通子图被称为强连通分量。

在上文中，一个强连通子图 G'=(V',E')(V\subseteq V,E'\subseteq E) 极大，当且仅当不存在包含 G' 的更大子图 G''=(V'',E'') 满足 V'\subseteq V''\subseteq V,E'\subseteq E''\subseteq E。显然，一个环一定是强连通图，所以我们的思路就是找到能和某个点构成环的所有点。

正如本文的 URL，强连通分量简记为 \text{SCC(Strongly Connected Component)}。

求 \text{SCC} 可以用 Tarjan，Kosaraju 或者 Garbow 算法，本文使用 Tarjan 算法。

定义：

(\operatorname{int})Time：当前时间戳；
(\operatorname{int})tot：\text{SCC} 的个数；
(\operatorname{int})dfn(u)：点 u 的 dfs 序；
(\operatorname{int})low(u)：以下节点的 dfn 的最小值：v\in subtree(u)（u 的子树）及从 v 出发通过一条不在搜索树上的边（非树边）能到达的节点；
(\operatorname{int})c(u)：记录点 u 所在的 \text{SCC}；
(\operatorname{stack}<\operatorname{int}>)sta：一个栈；
(\operatorname{bool})ins(u)：点 u 是否在 sta 中；
(\operatorname{vector}<\operatorname{int}>)scc(i)：记录编号为 i 的 \text{SCC} 内的所有节点。

Tarjan 算法使用 dfs 实现：

记录 dfn,low；
当前节点进栈；
更新 low：
更新后，如果 dfn(u)=low(u)，说明从 u 出发最终又能回到 u，即构成了环，是一个满足要求的 \text{SCC}。将 tot\gets tot+1，同时不停地弹栈直到弹到 u，则弹出的所有节点都在 subtree(u) 内；记录其在第 tot 个 \text{SCC} 内；最后将其加入 scc(tot) 中。

对于题目的特殊要求要求：

第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。

开一个 (\operatorname{bool})vis 数组记录每个 \text{SCC} 是否已经输出过即可。

每个强连通分量按节点编号大小输出

------------ $\text{Code}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#define re register
using namespace std;

inline int read()
{
    re int x = 0, f = 0;
    re char c = getchar();
    while (c < '0' || c > '9')
    {
        f |= c == '-';
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ '0');
        c = getchar();
    }
    return f ? -x : x;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 ^ '0');
}

inline int min2(int x, int y)
{
    return x < y ? x : y;
}
//-----------------------------------------------------------
const int MAXN = 1e4 + 5;
const int MAXM = 1e5 + 5;

int cnt, Time, tot;
int head[MAXN], dfn[MAXN], low[MAXN], c[MAXN];
bool ins[MAXN], vis[MAXN];
stack<int> sta;
vector<int> scc[MAXN];

struct edge
{
    int to, nxt;
}e[MAXM];

void add(int u, int v)
{
    e[++cnt] = edge{v, head[u]};
    head[u] = cnt;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++Time; //初始化
    sta.push(u); //进栈
    ins[u] = true; //标记
    for (re int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to; //更新
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min2(low[u], low[v]);
        }
        else if (ins[v])
        {
            low[u] = min2(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) //构成了环
    {
        tot++;
        int v = 0;
        while (u != v)
        {
            v = sta.top(); //弹栈
            sta.pop();
            ins[v] = false; //取消标记
            c[v] = tot;
            scc[tot].push_back(v); //记录答案
        }
    }
}

int main()
{
    int n = read(), m = read();
    for (re int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        add(u, v);
    }
    for (re int i = 1; i <= n; i++)
    {
        if (!dfn[i]) //防止不连通
        {
            tarjan(i);
        }
    }
    write(tot);
    putchar('\n');
    for (re int i = 1; i <= n; i++)
    {
        int x = c[i];
        if (vis[x])
        {
            continue;
        }
        vis[x] = true; //已输出过
        sort(scc[x].begin(), scc[x].end());
        for (re int i = 0; i < scc[x].size(); i++)
        {
            write(scc[x][i]);
            putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}