三色 dfs

SkyWave · 2025-01-02 22:45:43 · 算法·理论

初次相遇

CF2043E 官方题解，将这种算法称为 "three-colored DFS"。

作用

在有向图上找出一个简单环，或报告无环。

实现

实现一个递归函数 dfs(u)，其中参数 u 为一个结点的编号，函数返回值为是否有环。

定义一个栈 stk，实时维护当前在 dfs 栈中的所有结点编号，按被 dfs 访问的时的时间戳排序。若图上存在简单环，则保证函数结束时 stk 从底到顶保存了图上任意一个简单环的所有结点的任意一个环排列。

对于每个结点，定义三种状态：

该结点未被 dfs 访问过
该结点被 dfs 访问过且在 dfs 栈中
该结点被 dfs 访问过且不在 dfs 栈中

每个结点的初始状态为 0。

调用 dfs(u) 时需要保证 u 的状态为 0。

dfs(u) 步骤如下：

将 u 加入 stk
将 u 的状态设为 1
遍历 u 的所有出点 v。
- 若 v 的状态为 0：
  - 若 dfs(v) 返回有环，则返回有环
- 否则若 v 的状态为 1：
  1. 将早于 v 加入 stk 的所有结点从 stk 中删除
  2. 返回有环
将 stk 的栈顶（此时一定是 u）弹出
将 u 的状态设为 2
返回无环

算法主体步骤如下：

遍历给定图的所有结点 i
- 若 i 状态为 0
  - 若 dfs(i) 返回有环
    1. 报告有环，stk 即为图上任意一个简单环的所有结点的任意一个环排列
    2. 退出算法
报告无环
退出算法

时空复杂度

设 n,m 分别为输入的有向图的点数与边数。

时间复杂度：O(n + m)

空间复杂度：O(n)

证明

时空复杂度不用证明。

要证明算法正确性，就是要证明如下命题成立：若图中存在简单环，则必定存在一个简单环由若干条树边与恰好一条返祖边构成。

严谨证明见：xzf_200906 的证明。感谢 @xzf_200906 的贡献！

例题

Library Checker - Cycle Detection (Directed)

简要题意

给定一张 N 个点 M 条边的有向图，请以任意顺序给出图上任意一条回路的所有边。

解法

简单环也叫简单回路，故存在回路则一定存在简单环。所以考虑先使用三色 dfs，求出任意一个简单环的所有结点的任意一个环排列，设求出的一个简单环环长为 l。

接着对于 1 \leq i \leq l，遍历求出的环排列的第 i 个结点的所有出点，若出点为第 i \mod l + 1 个结点，则输出这条边的编号。

因为求出的环排列不会存在重复的结点，所以枚举这些结点的所有出点的时间复杂度为均摊 O(N + M)。

于是就在 O(N + M) 的时空复杂度下正确地完成了此题。

代码

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

constexpr int N = 500000 + 1, M = 500000 + 1;

int edge[M][2], tail[N], stk[N];
char vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        ++u; ++v;

        edge[i][0] = v; edge[i][1] = tail[u];
        tail[u] = i;
    }

    int top = 0;
    auto dfs = [&](auto &&self, int u) -> bool {
        vis[u] = 1;
        stk[++top] = u;

        for (int i_ = tail[u]; i_; i_ = edge[i_][1]) {
            int v = edge[i_][0];
            if (!vis[v]) {
                if (self(self, v)) {
                    return true;
                }
            } else if (vis[v] == 1) {
                for (int i = 1; i <= top; ++i) if (stk[i] == v) {
                    memmove(stk + 1, stk + i, sizeof(int) * (top -= i - 1));
                    break;
                }
                return true;
            }
        }

        --top;
        vis[u] = 2;
        return false;
    };

    for (int i = 1; i <= n; ++i) if (!vis[i] && dfs(dfs, i)) {
        break;
    }
    if (!top) {
        cout << "-1\n";
        return 0;
    }

    cout << top << '\n';
    for (int i = 1; i < top; ++i) {
        for (int j_ = tail[stk[i]]; j_; j_ = edge[j_][1]) {
            if (edge[j_][0] == stk[i + 1]) {
                cout << j_ - 1 << '\n';
                break;
            }
        }
    }
    for (int j_ = tail[stk[top]]; j_; j_ = edge[j_][1]) {
        if (edge[j_][0] == stk[1]) {
            cout << j_ - 1 << '\n';
            break;
        }
    }       
    return 0;
}

优缺点

最主要的优点是不用进行 tarjan 或使用其他算法求出强连通分量就可以找出环，常数较为优秀，实现较为简短。

实际上该算法就是 tarjan 的弱化版，和 tarjan 同样利用了 dfs 生成树上返祖边的性质。

只不过判定是否有环（是否是 dag）常数并不如拓扑排序。