请用C++代码实现DFS除环
时间: 2024-02-24 10:55:40 浏览: 19
好的,以下是使用C++实现DFS除环的代码:
```cpp
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, num, tot;
int head[MAXN], dfn[MAXN], low[MAXN], stk[MAXN];
bool vis[MAXN], ins[MAXN];
struct Edge {
int to, next;
} edge[MAXN << 1];
inline void add_edge(int u, int v) {
edge[++tot].to = v;
edge[tot].next = head[u];
head[u] = tot;
}
void tarjan(int u) {
dfn[u] = low[u] = ++num;
vis[u] = ins[u] = true;
stk[++stk[0]] = u;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (ins[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
int v;
do {
v = stk[stk[0]--];
ins[v] = false;
} while (v != u);
}
}
int main() {
cin >> n >> m;
tot = 1;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
return 0;
}
```
代码中使用了DFS除环来找出无向图中的所有环,具体实现过程如下:
1. 首先进行图的输入,并将边存储到邻接表中;
2. 定义一个栈,用于存储访问过的节点;
3. 对于每个未被访问过的节点u,进行如下处理:
- 对u进行DFS遍历;
- 在回溯时,如果u的某个邻接节点v的dfn值大于等于u,则说明(u,v)是环的一部分,将(u,v)加入栈中;
- 如果u是环的起点,则将栈中的所有元素弹出,构成一个环;
4. 重复步骤3,直到所有的节点都被访问过。
希望能够帮助到你!