【OI考古】图论 | 强连通分量 SCC | 缩点

简介

强连通分量（Strongly Connected Components）指有向图 $G$ 中的极大子图，其满足子图内所有顶点都可以互相到达。

强连通分量是有向图 $G$ 上的一种等价关系，每个 SCC 可以缩成一个点，便于后续的处理。

顺便吐槽一下最近在学校学的图论：把“连通分量”称为“连通分支”我忍了，把“二分图”称为“偶图”我也忍了，把“二叉树”叫“二元树”是什么鬼。虽然在图论学界术语不统一的背景下，对对象的称呼仅仅是习惯问题，但血压依然上来了（（

模板题 | P3916 | 图的遍历

题目描述

给出 $N$ 个点， $M$ 条边的有向图，对于每个点 $v$ ，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

输入格式

第 $1$ 行， $2$ 个整数 $N$ , $M$ 。接下来 $M$ 行，每行 $2$ 个整数 $U_i$ , $V_i$ ，表示边 $(U_i,V_i)$ 。点用 $1, 2, \cdots , N$ 编号。

输出格式

$N$ 个整数 $A(1), A(2) , \cdots , A(N)$ 。

输入输出样例

输入

输出

4 4 3 4

说明/提示

说明/提示

对于 $60\%$ 的数据， $1 \le N , \ M \le 10^3$ ；
对于 $100\%$ 的数据， $1 \le N , M \le 10^5$ 。

Tarjan 算法

没错，又是 Tarjan 算法，不过不是求 LCA 的 Tarjan 算法。

DFS 生成树

顾名思义，对着图 $G$ 做 DFS 的时候生成的树。

此过程会生成几种可能的边：

树边（tree edge）：绿色边，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
反祖边（back edge）：黄色边，也被叫做回边，即指向祖先结点的边。
横叉边（cross edge）：红色边，它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先时形成的。
前向边（forward edge）：蓝色边，它是在搜索的时候遇到子树中的结点的时候形成的。

求 SCC

主要维护两个变量：

dfn[u]表示 DFS 过程中u是第几个被遍历的节点。
low[u]表示以u为根的子树中，dfn值最小的节点，或通过返祖边、横叉边所能到达的dfn值最小的节点。

依据此思路，DFS 过程中的做法就很显然了，当搜索到节点u时，令其入栈，对于与u邻接的节点v：

如果v未被访问过，则v是u的子节点，对v进行 DFS，回溯时令low[u] = min(low[u], low[v])。
如果v已被访问过，且在栈中，则令low[u]=min(low[u],dfn[v])
如果v已被访问过，但不在栈中，说明这个节点的 SCC 信息已经被处理完了，不用管了。

解决方案

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1050;
int n, cc, tot, top, scc, st, end;
int head[maxn], dfn[maxn], low[maxn], stk[maxn], belong[maxn];
bool instk[maxn];
struct Node
{
    int to, next, from;
} edge[maxn * maxn];
void addedge(int u, int v)
{
    ++cc;
    edge[cc].from = u;
    edge[cc].to = v;
    edge[cc].next = head[u];
    head[u] = cc;
}
void tarjan(int u)
{
    low[u] = dfn[u] = ++tot;
    stk[++top] = u;
    instk[u] = true;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        ++scc;
        int v;
        do
        {
            v = stk[top--];
            belong[v] = scc;
            instk[v] = false;
        } while (v != u);
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int to;
        scanf("%d", &to);
        while (to != 0)
        {
            addedge(i, to);
            scanf("%d", &to);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i);
    }
    return 0;
}