拓扑排序与图的连通性问题

在图中，如何判断一张图是否连通？如果删掉某条边，它还连通吗？有向图呢？这些操作有什么特殊性质吗？本文将探讨以 Tarjan 算法为核心的有关图的连通性的问题和欧拉路问题。

除了 Tarjan 算法，并查集等内容也能解决一些图连通性问题，请参照笔者相关文章。

拓扑排序

~~别问我为什么把这个放到这里来讲，因为接下来很多题都要用到它。~~

严格意义上来说，拓扑排序不是一种排序。是对有向无环图（DAG） $G$ ，将 $G$ 中所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$ ，若它们之间存在一条有向边 $(u,v)$ ,则 $u$ 在线性序列中出现在 $v$ 之前。

模板。

开一个队列记录所有入度为 $0$ 的点，然后维护即可。这一过程被称之为 Kahn 算法。

查看代码

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

int n, m;
int in[105];
vector<int> G[105];
queue<int> q;

int main(void) {
    while (scanf("%d%d", &n, &m) == 2 && n) {
        memset(in, 0, sizeof(in));
        for (int i = 1; i <= n; ++i) G[i].clear();
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            ++in[y];
        }
        for (int i = 1; i <= n; ++i)
            if (in[i] == 0) q.push(i);
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            printf("%d ", t);
            for (int i = 0; i < G[t].size(); ++i) {
                --in[G[t][i]];
                if (in[G[t][i]] == 0) q.push(G[t][i]);
            }
        }
        putchar('\n');
    }
    return 0;
}

拓扑排序也可以使用 dfs 实现，感兴趣的读者可以自行学习。

有的时候求的拓扑序要求字典序，这时候直接将队列改为优先队列即可。

无向图的连通性

给定无向图 $G=(V,E)$ ，如果 $x\in V$ ，从图中删去节点 $x$ 和与 $x$ 关联的所有边之后， $G$ 被分裂成两个或两个以上的不相连的子图，那么称 $x$ 称之为 $G$ 的割点或割顶。如果 $e\in V$ ，将 $e$ 删去后， $G$ 分裂成两个不相连的子图，则称 $e$ 为 $G$ 的桥或割边。

我们可以使用 Tarjan 算法在线性时间内求解无向图的割点和桥。

想要使用 Tarjan 算法，我们需要先了解几个基本概念：

Tarjan 算法

时间戳。我们对图进行深度优先遍历，按照每个节点第一次被访问到的顺序，依次给予 $n$ 个节点 $1\sim n$ 的整数标记，记为时间戳 $dfn[x]$ ，代表在 DFS 序中出现的位置。

搜索树。在无向连通图中任选一个节点出发进行深度优先遍历，每个点只访问一次，所有发生递归的边 $(x,y)$ （即 $x$ 到 $y$ 是对 $y$ 的第一次遍历），这样的边有 $n-1$ 条，构成一棵树，称之为”无向连通图的搜索树“。如果这张图不连通，那么它会生成若干棵树，称之为”无向图的搜索森林“。

追溯值。除了时间戳外，还有一个概念：追溯值 $low[x]$ ，也就是能不经过父亲节点到达的最小时间戳。设 $\text{subtree}(x)$ 代表搜索树中以 $x$ 的子树， $low[x]$ 定义为以下节点的时间戳的最小值：

$\text{subtree}(x)$ 中的节点；
通过 $1$ 条不在搜索树上的边，可以到达 $\text{subtree}(x)$ 的节点。

这是一张无向图，粗边标出了搜索树，1 为根节点，每个节点是它的时间戳，括号标出了它的追溯值

如上图， $1$ 节点的追溯值是它自己的时间戳， $(1,5)$ 一条不在搜索树上的边使得 $low[5]=dfn[1]=1$ ，所以 $2,3,4$ 节点都是 $5$ 的祖先，又因为 $(1,5)$ 这条边，所以 $low[2]=low[3]=low[4]=dfn[1]=1$ 。剩余节点大致同理。

我们计算追溯值时，应该首先令 $low[x]=dfn[x]$ ，然后考虑 $x$ 出发的每条边 $(x,y)$ ：如果在搜索树上 $x$ 是 $y$ 的父亲，那么 $low[x]=\min\{low[x], low[y]\}$ ；如果 $(x,y)$ 不是搜索树上的边，则 $low[x]=\min\{low[x], dfn[y]\}$ 。

Tarjan 的时间复杂度为 $O(n+m)$ 。

至于追溯值究竟是怎么来的，读者可以自行查阅资料。

割边判定法则

无向边 $(x,y)$ 是割边，当且仅当搜索树上存在一个 $x$ 的子节点 $y$ ，满足 $dfn[x]<low[y]$ 。也就是说从 $\text{subtree}(y)$ 出发，若不经过 $(x,y)$ ，怎么走都无法到达 $x$ 或比 $x$ 更早访问的节点（因为 $dfn[x]<low[y]$ ，即想要到 $y$ 必须经过 $(x,y)$ ，即 $y$ 被困在 $x$ 的子树中了），那么这条边便是桥。

可以发现，桥一定是搜索树中的边，并且一个简单环中的边一定都不是桥。

虚线标出了桥

在存边的时候使用了一个 edges 数组，这样使用”成对变换“可以轻松的找到反向边。记录 fa 的话遇到重边时会出错。

查看代码

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

int n, m, num = 0; // num 用于时间戳的标记
int dfn[105], low[105];

struct edge {
    int from, to;
    edge(int from = 0, int to = 0) :
        from(from), to(to) {}
};

vector <edge> edges;
bool bridge[205];
vector <int> G[105];

inline void addedge(int u, int v) {
    edges.push_back(edge(u, v));
    G[u].push_back(edges.size() - 1);
}

void tarjan(int x, int in_edge) { // in_edge 记录递归进入 x 的边的编号
    dfn[x] = low[x] = ++num; // 标记时间戳，并在初始将 low[x] 标记为 dfn[x]
    for (int i = 0; i < G[x].size(); ++i) {
        int y = edges[G[x][i]].to; // 获取边 (x,y)
        if (!dfn[y]) { // 未访问
            tarjan(y, G[x][i]); // 递归遍历
            // 能跑到这里的肯定是搜索树上的
            // 所以 x 是 y 的父亲节点了，也就是 y 属于 subtree(x)
            low[x] = min(low[x], low[y]);
            // 割边判定法则，在搜索树上存在 x 的一个子节点 y 使得 dfn[x] < low[y]
            if (dfn[x] < low[y]) bridge[G[x][i]] = bridge[G[x][i] ^ 1] = true; // 标记的时候标记正边和反边
        }
        else if (G[x][i] != (in_edge ^ 1)) low[x] = min(low[x], dfn[y]);
        // 如果当前这条边是 x->y 的反边 y->x，那么这条命令不会被执行，因为它在搜索树上
        // 但是有重边的话他就不是搜索树上的边
    }
}

int main(void) {
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v), addedge(v, u);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i, -1); // 图不一定连通，每个点都需要 tarjan。最初没有边到 i，用 -1 代替，-1 ^ 1 = -2
    puts("Bridges:");
    for (int i = 0; i < edges.size(); i += 2)
        if (bridge[i]) printf("%d %d\n", edges[i].from, edges[i].to);
    return 0;
}

割点判定法则

模板。

如果 $x$ 不是搜索森林中一棵树的根节点，那么 $x$ 是割点当且仅当搜索树上存在 $x$ 的子节点 $y$ 满足 $dfn[x]\le low[y]$ 。如果这是根节点，这样的 $y$ 必须有两个或以上， $x$ 才是割点。

由于是小于等于，所以父节点和重边即使不考虑也能得到正确结果。

查看代码

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

int n, m, root, num = 0, ans = 0;
int dfn[20005], low[20005];

struct edge {
    int from, to;
    edge(int from = 0, int to = 0) :
        from(from), to(to) {}
};

vector <edge> edges;
bool cut[20005];
vector <int> G[20005];

inline void addedge(int u, int v) {
    edges.push_back(edge(u, v));
    G[u].push_back(edges.size() - 1);
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = edges[G[x][i]].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) {
                ++flag;
                if (x != root || flag > 1) cut[x] = true; // 如果不是根节点，或者 flag >= 2，就是割点
            }
        }
        else low[x] = min(low[x], dfn[y]); // 可以直接更新
    }
}

int main(void) {
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v), addedge(v, u);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) root = i, tarjan(i); // 记录根节点，然后 tarjan
    for (int i = 1; i <= n; ++i)
        if (cut[i]) ++ans;
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i)
        if (cut[i]) printf("%d ", i);
    putchar('\n');
    return 0;
}

拓扑排序与图的连通性问题

拓扑排序

无向图的连通性

Tarjan 算法

割边判定法则

割点判定法则

[POI2008] BLO-Blockade

双连通分量与缩点

e-DCC 及其缩点

v-DCC 及其缩点

有向图的连通性

Tarjan 算法

缩点

2-SAT 问题

欧拉图

概述

Hierholzer 算法

哈密顿图

Problemset

拓扑排序

[Luogu P1347] 排序

[Luogu P1113] 杂务

[HNOI2015] 菜肴制作

[CSP-S2020] 函数调用

连通性问题

[Luogu P2002] 消息扩散

[USACO03FALL] 受欢迎的牛 G

[USACO5.3] Network of Schools

[APIO2009] 抢掠计划

[Luogu P2656] 采蘑菇

[USACO06JAN] Redundant Paths G

连通性的应用

[CF1777E] Edge Reverse

[NOI2017] 游戏

[yLOI2018] 锦鲤抄

[CF51F] Caterpillar

欧拉路问题

[Luogu P1341] 无序字母对

[CF1152E] Neko and Flashback

[CF36E] Two Paths