无向图寻找环的方法:
(一) DFS
DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。该算法的复杂度为O(V)。
#include <cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=100010;
vector<int> graph[MAXN];
int vis[MAXN];
bool dfs(int u,int fa)
{
int n=graph[u].size();
for(int i=0;i<n;i++)
{
int v=graph[u][i];
if(v==fa) continue;
if(vis[v]==0)
{
vis[v]=1;
if(dfs(v,u)) return true;
}
else return true;
}
return false;
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(graph,0,sizeof(graph));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
}
memset(vis,0,sizeof(vis));
int flag=0;
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
vis[i]=1;
if(dfs(i,-1))
{
flag=1;
break;
}
}
}
if(flag) printf("has circle\n");
else printf("no cycle\n");
}
}
( 二 ) 并查集
每遇到一条边，判断这边的两个端点是否在同一个集合里？
在的话，表示有环：因为两个点在一个集合里就表示这两个点已经有一条路径了，现在再加一条路径，必然构成环。
不在的话，表示不构成环，我们应该合并这两个集合：因为加上这条边，两个集合就被连起来了，合并成了一个集合
#include <cstdio>
using namespace std;
const int MAXN=100010;
int father[MAXN];
int grade[MAXN];
int cnt;
int parent(int u)
{
while(u!=father[u])
{
father[u]=father[father[u]];
u=father[u];
}
return u;
}
bool connect(int u,int v)
{
int fu=parent(u);
int fv=parent(v);
if(fu==fv) return false;
if(grade[fu]>grade[fv])
{
father[fv]=fu;
grade[fu]+=grade[fv];
}
else
{
father[fu]=fv;
grade[fv]+=grade[fu];
}
cnt--;
return true;
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=n;i++) grade[i]=1;
cnt=n;
bool flag=false;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(!connect(a,b)) flag=true;
}
if(flag) printf("has circle\n");
else printf("no cycle\n");
}
}
有向图寻找环的方法
( 一 ) DFS
如果目前访问的节点还在栈中,说明有向图存在环
vis[0]代表没访问的节点,vis[1]代表访问过的不在栈中的节点,vis[2]代表在栈中的节点
#include <cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=100010;
vector<int> graph[MAXN];
int vis[MAXN];
bool dfs(int u)
{
if(vis[u]==2) return true;
vis[u]=2;
int n=graph[u].size();
for(int i=0;i<n;i++)
{
int v=graph[u][i];
if(vis[v]==0)
{
if(dfs(v)) return true;
}
else if(vis[v]==2) return true;
}
vis[u]=1;
return false;
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(graph,0,sizeof(graph));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
}
memset(vis,0,sizeof(vis));
int flag=0;
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
if(dfs(i))
{
flag=1;
break;
}
}
}
if(flag) printf("has circle\n");
else printf("no cycle\n");
}
}
拓扑排序的步骤：
- 1.从 图中选择一个 没有前驱（即入度为0）的顶点并输出。
- 2.从图中删除该顶点和所有以它为起点的有向边。
重复 1 和 2 直到当前的图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
拓扑排序可以完成的条件是图最后是空的
#include <cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=100010;
vector<int> graph[MAXN];
int in[MAXN];
bool topoSort(int n)
{
vector<int> zero;
for(int i=1;i<=n;i++)
{
if(in[i]==0) zero.push_back(i);
}
int sum=0;
while(!zero.empty())
{
int curr=zero.back();
zero.pop_back();
sum++;
int len=graph[curr].size();
for(int i=0;i<len;i++)
{
int v=graph[curr][i];
in[v]--;
if(in[v]==0) zero.push_back(v);
}
}
return sum!=n;//有环
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(graph,0,sizeof(graph));
memset(in,0,sizeof(in));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
in[b]++;
}
if(topoSort(n)) printf("has circle\n");
else printf("no cycle\n");
}
}
附录:
有向图是否存在负环的方法:
Bellman_Ford
SPFA
Floyd_Warshall
