【概述】

有向无环图（Directed Acyclic Graph），即 DAG 图，是指任意一条边有方向且不存在环路的图。

判断 DAG 图的方法有：拓扑排序 O(E)、Bellman-Ford 算法 O(VE)、使用邻接表的 DFS O(V+E) 等

【拓扑排序】

拓扑排序过程如果能生成 n 个顶点序列，那么说明图中不存在环，即图是一个 DAG 图

关于拓扑排序：点击这里

struct Node{ int x; int num; Node(){} Node(int x,int num):x(x),num(num){} }; vector<Node> edge[N]; int vis[N]; int n,m; bool dfs(int x,int m){ if(vis[x]==1)//出环 return true; if(vis[x]==-1)//已访问 return false; vis[x]=1;//正在被占用 for(int i=0;i<edge[x].size();i++) if(edge[x][i].num<=m&&dfs(edge[x][i].x,m)) return true; vis[x]=-1;//解除占用并标记访问 return false; } bool judge(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) if(!vis[i]&&dfs(i,m)) return true; return false; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; edge[x].push_back(Node(y,i)); } if(judge()) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }

【Bellman-Ford 算法】

由于 Bellman-Ford 算法除求最短路外只能判断是否存在负环，因此可以先把权值设为 -1，再进行判断

关于 Bellman-Ford 算法：点击这里

struct Node{ int x,y; int w; }G[N*2]; int dis[N]; bool ford(int n, int m){ for(int i=1;i<n;i++){ for(int j=0;j<m;j++){ int x=G[j].x; int y=G[j].y; int w=G[j].w; if(dis[y]>dis[x]+w) dis[y]=dis[x]+w; } } for(int i=0;i<m;i++) if(dis[G[i].x]>dis[G[i].y]+G[i].w) return true; return false; } int main(){ int n,m; scanf("%d%d",&n,&m); memset(dis,INF,sizeof(dis)); for(int i=0;i<m;i++){ scanf("%d%d",&G[i].x,&G[i].y); G[i].w=-1;//把权值全部改为-1 if(G[i].x==0) dis[G[i].y]=-1; } if(ford(n,m)) printf("NO\n"); else printf("YES\n"); return 0; }

【使用邻接表的 DFS】

枚举起点进行 DFS，如果当某个点与起点相同，则说明存在环，即非 DAG 图 

struct Edge{ int next; int to; }edge[N*2]; int cnt,head[N],son[N]; bool vis[N]; void add(int from,int to){ edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt; } bool flag; void dfs(int x){ if(vis[x]) flag=false; if(!flag) return; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next) dfs(edge[i].to); vis[x]=false; } int main(){ int n,m; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); for(int i=0;i<m;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++){ flag=true; dfs(i); if(!flag) break; } if(flag) printf("Yes\n"); else printf("No\n"); return 0; }