[图论]判环的几种方法 |
您所在的位置：网站首页 › 上环方法 › [图论]判环的几种方法 |
|
判环的几种方法
拓扑排序判环
对于有向图：
//有向图环判断
#include
using namespace std;
vectoredge[10001];
int n,m,d[10001];
queueq;
inline void TopoSort()
{
int cnt = 0;
for(int i = 1;ix>>y;
edge[x].push_back(y);
++d[y];
}
TopoSort();
return 0;
}
/*
4 4
1 2
2 3
3 4
1 4
No
*/
对于无向图
因为是双向边，那么我们需要先把度数为\(1\)的点加入(区别与上面有向图(度数为0的加入))队列， for(int i = 1; i v; e[u].push_back(v); e[v].push_back(u); d[u]++; d[v]++; } toposort(); sets; for(int i = 1;i 1)s.insert(i); for(auto x : s) cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |