三色 dfs

· · 算法·理论

初次相遇

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

作用

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

实现

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

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

对于每个结点,定义三种状态:

  1. 该结点未被 dfs 访问过
  2. 该结点被 dfs 访问过且在 dfs 栈中
  3. 该结点被 dfs 访问过且不在 dfs 栈中

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

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

dfs(u) 步骤如下:

  1. u 加入 stk

  2. u 的状态设为 1

  3. 遍历 u 的所有出点 v

    • v 的状态为 0:

      • dfs(v) 返回有环,则返回有环
    • 否则若 v 的状态为 1:

      1. 将早于 v 加入 stk 的所有结点从 stk 中删除

      2. 返回有环

  4. stk 的栈顶(此时一定是 u)弹出

  5. u 的状态设为 2

  6. 返回无环

算法主体步骤如下:

  1. 遍历给定图的所有结点 i

    • i 状态为 0

      • dfs(i) 返回有环

        1. 报告有环,stk 即为图上任意一个简单环的所有结点的任意一个环排列
        2. 退出算法
  2. 报告无环

  3. 退出算法

时空复杂度

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)常数并不如拓扑排序。