拓扑排序一遍就好了
记住,图不一定是联通时,一定要把每个入度为零的节点跑一遍!!!
核心代码如下:
int in[N],timeq=0,n,m;//timeq 时间戳
int vis[N];//标记数组
inline bool dfs(int u){//u 当前节点
bool flag=false;//flag 标记
for(int i=head[u];i;i=e[i].next){//领接表遍历图
int v=e[i].to;
if(timeq==vis[v]) return true;//当前边是返祖边,则有环
else if(vis[v]) return false;//上次遍历过了且不是这次遍历产生的,一定没有环
flag=dfs(v);//遍历
if(flag) return true;
}
return false;
}
int main(){
scanf("%d%d",&n,&m);//n 节点数 m 边数
for(int i=1;i<=m;i++){
int x,y,val;
scanf("%d%d%d",&x,&y,&val);// x->y的边权值为val
add(x,y,val);//邻接表存边
in[y]++;//统计入度
}
for(int i=1;i<=n;i++)//顺次访问入度为0的节点
if(!in[i]){
vis[i]=++timeq;//标记访问次数
if(dfs(i)){//遍历
printf("Yes");//有环
return 0;
}
}
printf("No");//无环
}
这时,我们就要用SPFA(此处所讲的是dfs版),其实可以用堆优化,但是作者懒,在这不想写
其实也么什么好讲的,主要看毒瘤出题人有没有给重边和自环代码实现
下面的代码包含处理重边和自环的情况:
#include<stdio.h>
#define N 2007
using namespace std;
#define INF 0x3f3f3f3f
struct E{
int next,to,dis;
}e[N<<2];
int head[N],cnt=0,n,m,dis[N],st;
bool vis[N];
inline void read(int &x){
x=0;int flag=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
x*=flag;
}
inline void add(int id,int to,int dis){//存图
cnt++;
e[cnt].next=head[id];
e[cnt].to=to;
e[cnt].dis=dis;
head[id]=cnt;
}
inline bool dfs(int u){
vis[u]=true;//标记已访问过
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(u==v&&e[i].dis<0) return true;//如果是自环且dis小于0,此环定是负环
if(dis[v]>dis[u]+e[i].dis){//更新
if(vis[v]) return true;//如果访问过且这次又更新了,一定有负环
dis[v]=dis[u]+e[i].dis;
if(dfs(v)) return true;//往下遍历
}
}
vis[u]=false;//回溯
return false;//返回没有环
}
int main(){
read(n);read(m);read(st);//st 源点
for(int i=1;i<=n;i++)
dis[i]=INF,vis[i]=false;//初始化 dis 到源点的最短路距离 vis 标记数组
for(int i=1;i<=m;i++){
int x,y,dis;
read(x);read(y);read(dis);
add(x,y,dis);
}
dis[st]=0;//初始源点到自身距离为0
bool flag=dfs(st);
if(flag) printf("Yes\n");
else printf("No\n");
}
无向图就更简单了
直接遍历一遍,如果遇到返祖边则判断一下当前记录的dis[u]+e[i].dis是否为负
如果是,则一定有负环,否则当前没有负环,回溯
其余情况直接往下遍历就是了,没有过多技巧,这里就不再赘述