三色 dfs
初次相遇
CF2043E 官方题解,将这种算法称为 "three-colored DFS"。
作用
在有向图上找出一个简单环,或报告无环。
实现
实现一个递归函数 dfs(u)
,其中参数
定义一个栈
对于每个结点,定义三种状态:
- 该结点未被 dfs 访问过
- 该结点被 dfs 访问过且在 dfs 栈中
- 该结点被 dfs 访问过且不在 dfs 栈中
每个结点的初始状态为 0。
调用 dfs(u)
时需要保证
dfs(u)
步骤如下:
-
将
u 加入stk -
将
u 的状态设为 1 -
遍历
u 的所有出点v 。-
若
v 的状态为 0:- 若
dfs(v)
返回有环,则返回有环
- 若
-
否则若
v 的状态为 1:-
将早于
v 加入stk 的所有结点从stk 中删除 -
返回有环
-
-
-
将
stk 的栈顶(此时一定是u )弹出 -
将
u 的状态设为 2 -
返回无环
算法主体步骤如下:
-
遍历给定图的所有结点
i -
若
i 状态为 0-
若
dfs(i)
返回有环- 报告有环,stk 即为图上任意一个简单环的所有结点的任意一个环排列
- 退出算法
-
-
-
报告无环
-
退出算法
时空复杂度
设
时间复杂度:
空间复杂度:
证明
时空复杂度不用证明。
要证明算法正确性,就是要证明如下命题成立:若图中存在简单环,则必定存在一个简单环由若干条树边与恰好一条返祖边构成。
严谨证明见:xzf_200906 的证明。感谢 @xzf_200906 的贡献!
例题
Library Checker - Cycle Detection (Directed)
简要题意
给定一张
解法
简单环也叫简单回路,故存在回路则一定存在简单环。所以考虑先使用三色 dfs,求出任意一个简单环的所有结点的任意一个环排列,设求出的一个简单环环长为
接着对于
因为求出的环排列不会存在重复的结点,所以枚举这些结点的所有出点的时间复杂度为均摊
于是就在
代码
#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)常数并不如拓扑排序。