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

orz_z · 2021-08-02 15:30:41 · 题解

原题传送门

Tarjan 算法

1. 什么是 Tarjan

Tarjan 算法是一种用于求解有向图的强连通分量的算法，时间复杂度为 O(n + m)。它可以求出每个强连通分量的大小、属于其的顶点和强连通分量的总数。

2. 认识 dfs 生成树

dfs 生成树处理强连通分量的一个有力的工具：在 dfs 时，每当通过某条边 e 访问到一个新节点 v，就加入这个点和这条边，最后得到的便是 dfs 生成树。

例如下面这张有向图：

它的 dfs 生成树可能是这样（黑色实线）：

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

1. 树枝边（tree edge）：黑色实线，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
2. 前向边（forward edge）：灰色虚线，从某个点到它的某个子孙节点（注意不是子节点）的边。
3. 后向边（back edge）（也称反祖边）：绿色虚线，也被叫做回边，即指向祖先结点的边。
4. 横叉边（cross edge）：蓝色虚线，从某个点到一个已被访问过且既非它子孙节点、也非它祖先节点的边。

定理 1：后向边和横叉边都有一个特点：起点的 dfs 序必然大于终点的 dfs 序。

证：对于反向边，由于祖先节点的 dfs 序小于子孙节点，所以是显然的。对于横叉边 u→v，由于 v 既不是 u 的祖先，也不是 u 的子孙，所以必然存在一个不同于 u、v 的点 w=lca(u,v)，u 和 v 分别位于两个分支上。 u→v 没有成为一条树边，这说明 v 所在的分支一定在 u 所在的分支之前被访问过，也就是说，分别在 u 所在分支和 v 所在分支上任取点 p 和 q，前者的 dfs 序都一定比后者大，自然也有 dfsn(u)>dfsn(v)。得证。

这可以导出一个有用的结论：对于每个强连通分量，存在一个点是其他所有点的祖先。若不然，则可以把强连通分量划成 n 个分支，使各分支的祖先节点互相不为彼此的祖先。这些分支间不能通过树边相连，只能通过至少 n 条横叉边相连，但这必然会违背上一段讲的性质。

我们把这个唯一的祖先节点称为强连通分量的根。显然，根是强连通分量中 dfs 序最小的节点。

定理 2：如果结点 u 是某个强连通分量的根（也就是在在搜索树中遇到的第一个结点），那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中。

反证法：假设有个结点 v 在该强连通分量中但是不在以 u 为根的子树中，那么 u 到 v 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 u 是第一个访问的结点矛盾了。得证。

3. Tarjan 的基本思想

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

• 根据这样的定义，某个点 $p$ 是强连通分量的根，等价于 $low[p]=dfsn[p]$。 > 证明：如果 $low[p]=dfsn[p]$，说明 $p$ 不能到达 dfs 序比 $p$ 小的节点，或者说不存在一个强连通分量同时包含 $p$ 和某个 dfs 序比 $p$ 小的节点。因此，$p$ 只能是某个强连通分量的根。 我们这里必须强调 $v$ 可达 $u$，否则在下图中，会使 $low[5]=2$，但它是一个强连通分量的根。 

枚举图中的顶点 v，如果 dfsn_{v} = 0，说明 v 属于一个新的强连通分量，从 v 开始搜索。

接下来，按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中，对于以某个点 p 为起点的边 p \to q：

• 如果 q 未访问过，则 q 在 p 所在的子树上，如果某节点 r 从 q 起可以经过最多一条后向边到达，则从 p 起也可以（先从 p 到 q，再到 r），于是先递归处理点 q，然后令 low[p] = min(low[p], low[q])。
• 如果 q 已访问过，且从 q 可以到达 p，说明 q 是 p 的祖先且 p 可以通过一条非树边到达 q，则令 low[p] = min(low[p],dfsn[q])。
• 如果 q 已访问过，且从 q 不能到达 p，不做处理。（后两种情况都是非树边）。

但是我们怎么确认一个点能不能到达另一个点呢？因为反向边和横叉边都指向 dfs 序较小的节点，而前向边的存在又不影响状态转移方程，所以我们只需要确认比该点 dfs 序小的哪些点能到达该点即可，这可以用一个栈动态地维护：

• 每当搜索到新点，就令它入栈。

• 如果发现点 p 满足 low[p]=dfsn[p] ，则说明 p 是某个强连通分量的根，它和栈中的子孙节点相互可达。但同时，它和栈中的子孙节点也无法到达 p 的祖先节点，以及祖先节点其他尚未搜索的分支了，所以不断从栈顶弹出元素，直到弹出 p（注意这样维护的栈中节点的 dfs 序是单调增的），同时记录答案。

关于本题

对于每一个点，若没有遍历过，则跑一遍 dfs。

在弹出栈时，用 id_i 记录点 i 所处的强连通分量的编号。

题目还要求要排序输出，可以用一个动态数组存答案排序输出。

但笔者太懒了，就用了 O(n^2) 输出。

AC CODE

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005 * 2;

struct node
{
    int to, nxt;
} edge[maxn];

int n, m, mx = -1, cnt, cnt_node, cntn, head[maxn], dfn[maxn], low[maxn], id[maxn];
bool vis[maxn];
int opt[maxn];
stack<int> s;

inline void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

inline void tarjan(int u)
{
    cnt_node++;
    dfn[u] = low[u] = cnt_node;
    s.push(u);
    vis[u] = 1;
    for (int &e = head[u]; e; e = edge[e].nxt)
    {
        if (!dfn[edge[e].to])
        {
            tarjan(edge[e].to);
            low[u] = min(low[edge[e].to], low[u]);
        }
        else if (vis[edge[e].to])
            low[u] = min(low[u], dfn[edge[e].to]);
    }
    if (low[u] == dfn[u])
    {
        cntn++;
        while (1)
        {
            int now = s.top();
            s.pop();
            vis[now] = 0;
            id[now] = cntn;
            if (now == u)
                break;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    cout << cntn << endl;
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i]) continue;
        cout << i << " ";
        for(int j = 1; j <= n; ++j)
        {
            if(id[j] == id[i] && j != i)
            {
                cout << j << " ";
                vis[j] = 1;
            }
        }
        cout << endl;
    }
    return 0;
}