专栏文章

三色 dfs

SSkyWave
算法·理论参与者 10已保存评论 10

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
10 条
当前快照
1 份
快照标识符
@miqlm7bj
此快照首次捕获于
2025/12/04 06:48
3 个月前
此快照最后确认于
2025/12/04 06:48
3 个月前
查看原文

初次相遇

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

作用

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

实现

实现一个递归函数 dfs(u)，其中参数 uu 为一个结点的编号，函数返回值为是否有环。
定义一个栈 stkstk，实时维护当前在 dfs 栈中的所有结点编号，按被 dfs 访问的时的时间戳排序。若图上存在简单环，则保证函数结束时 stkstk 从底到顶保存了图上任意一个简单环的所有结点的任意一个环排列。
对于每个结点，定义三种状态：
  1. 该结点未被 dfs 访问过
  2. 该结点被 dfs 访问过且在 dfs 栈中
  3. 该结点被 dfs 访问过且不在 dfs 栈中
每个结点的初始状态为 0。
调用 dfs(u) 时需要保证 uu 的状态为 0。
dfs(u) 步骤如下：
  1. 将 uu 加入 stkstk
  2. 将 uu 的状态设为 1
  3. 遍历 uu 的所有出点 vv。
    • 若 vv 的状态为 0：
      • 若 dfs(v) 返回有环，则返回有环
    • 否则若 vv 的状态为 1：
      1. 将早于 vv 加入 stkstk 的所有结点从 stkstk 中删除
      2. 返回有环
  4. 将 stkstk 的栈顶（此时一定是 uu）弹出
  5. 将 uu 的状态设为 2
  6. 返回无环
算法主体步骤如下：
  1. 遍历给定图的所有结点 ii
    • 若 ii 状态为 0
      • 若 dfs(i) 返回有环
        1. 报告有环，stk 即为图上任意一个简单环的所有结点的任意一个环排列
        2. 退出算法
  2. 报告无环
  3. 退出算法

时空复杂度

设 n,mn,m 分别为输入的有向图的点数与边数。
时间复杂度：O(n+m)O(n + m)
空间复杂度：O(n)O(n)

证明

时空复杂度不用证明。
要证明算法正确性，就是要证明如下命题成立：若图中存在简单环，则必定存在一个简单环由若干条树边与恰好一条返祖边构成。
严谨证明见：xzf_200906 的证明。感谢 xzf_200906的贡献！

例题

Library Checker - Cycle Detection (Directed)

简要题意

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

解法

简单环也叫简单回路，故存在回路则一定存在简单环。所以考虑先使用三色 dfs，求出任意一个简单环的所有结点的任意一个环排列，设求出的一个简单环环长为 ll。
接着对于 1≤i≤l1 \leq i \leq l，遍历求出的环排列的第 ii 个结点的所有出点，若出点为第 imod  l+1i \mod l + 1 个结点，则输出这条边的编号。
因为求出的环排列不会存在重复的结点，所以枚举这些结点的所有出点的时间复杂度为均摊 O(N+M)O(N + M)。
于是就在 O(N+M)O(N + M) 的时空复杂度下正确地完成了此题。

代码

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

评论

共 10 条评论，欢迎与作者交流。

正在加载评论...