64 lines
1.8 KiB
C++
64 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
/**
|
||
5 5
|
||
|
||
1 2
|
||
2 3
|
||
2 5
|
||
3 4
|
||
3 1
|
||
|
||
对比上个例子，添加了一条3->1的边，就成了有向有环图.
|
||
本题，也就不能输出拓扑序了，因为有环图没有拓扑序，拓扑序是针对DAG的。可以判断是否有环。
|
||
*/
|
||
|
||
//本代码功能：以dfs判断一个有向图SDG是否有环
|
||
const int N = 1010;
|
||
|
||
int st[N]; //标识是不是已经使用过
|
||
vector<int> edge[N];//邻接表
|
||
int n; //n个结点
|
||
int m; //m个关系
|
||
|
||
/**
|
||
* 功能：深度优先搜索，判断以u开头的图中是否有环，有环：true,无环：false
|
||
有向有环图dfs判断是否有环只需要把st[]的状态改一下，原本是两种状态，0和1，
|
||
现在改成 0，1，-1
|
||
0:代表未访问
|
||
-1:代表访问完毕
|
||
1:代表是这一阶段正在访问的（这一阶段指的是两个元素在同一个递归中）。
|
||
*/
|
||
bool dfs(int u) {
|
||
//标识u结点正在访问
|
||
st[u] = 1;
|
||
|
||
//遍历每个出边,找到下一组结点
|
||
for (int v:edge[u]) {
|
||
//如果遇到了正在访问的结点，那么说明有环
|
||
if (st[v] == 1) return true;
|
||
//如果v这个结点没有访问过，递归查找v结点是否在环中
|
||
if (st[v] == 0 && dfs(v)) return true;
|
||
}
|
||
|
||
//标识u结点访问完毕
|
||
st[u] = -1;
|
||
return false;
|
||
}
|
||
|
||
int main() {
|
||
//读入，建图
|
||
cin >> n >> m;
|
||
for (int i = 1; i <= m; i++) {
|
||
int x, y;
|
||
cin >> x >> y;
|
||
edge[x].push_back(y);
|
||
}
|
||
//将所有未访问过的结点进行深入优先搜索判断是否有环
|
||
for (int i = 1; i <= n; i++)
|
||
if (!st[i] && dfs(i))//没有访问过，并且有环
|
||
cout << "发现环！" << endl;
|
||
return 0;
|
||
}
|