判断一个有向图是否有环

本文主要是介绍判断一个有向图是否有环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转自：http://blog.csdn.net/panhe1992/article/details/8366466

Description

给出一个有向图，判断图中是否存在回路。

Input

第 1 行：输入图的顶点个数 N （ 1 ≤ N ≤ 2,500 ）和 C （图的边数， 1 ≤ C ≤ 6,200 ）；

第 2 到 C+1 行中，第 i+1 行输入两个整数，分别表示第 i 条边的起点和终点的编号。

Output

如果图中存在回路，输出“ YES ”，否则，输出“ NO ”。

Sample Input

7 8

1 2

1 3

2 4

2 6

3 4

4 5

5 2

5 7

Sample

YES

大致的思路是深搜，将深搜的点加一个特殊标记，如果从当前的点往下搜的时候，发现了这个特殊标记，立刻判定有环。

代码如下

[cpp]  view plain copy  
 #include<cstdio>  
 #include<cstring>  
 int n,c,a[2600][2600],vis[2600],swi;  
 int dfs(int v){      
     vis[v] = -1;      
     for(int i = 1; i <= n; i++)      
     {          
         if(a[v][i] != 0 && !vis[i])  {            
             dfs(i);          
             vis[i]=1;  
         }  
         if(a[v][i] != 0 && vis[i] == -1){       
             printf("YES\n");  
             swi=true;  
             return true;      
         }  
     }      
     return false;  
 }  
 int main(){  
     memset(a,0,sizeof(a));  
     memset(vis,0,sizeof(vis));  
     swi=false;  
     scanf("%d %d",&n,&c);  
     int r1,r2;  
     for(int i=0;i<c;++i){  
         scanf("%d %d",&r1,&r2);  
         a[r1][r2]=1;  
     }  
     dfs(1);  
     if(!swi) printf("NO\n");  
 }  