判断一个有向图是否有环

今天药忘吃喽~ 2022-06-14 04:57 182阅读 0赞

转自：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][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  **int** n,c,a\[2600\]\[2600\],vis\[2600\],swi;  
4.  **int** dfs(**int** v)\{      
5.      vis\[v\] = -1;      
6.      **for**(**int** i = 1; i <= n; i++)      
7.      \{          
8.          **if**(a\[v\]\[i\] != 0 && !vis\[i\])  \{            
9.              dfs(i);          
10.             vis\[i\]=1;  
11.         \}  
12.         **if**(a\[v\]\[i\] != 0 && vis\[i\] == -1)\{       
13.             printf("YES\\n");  
14.             swi=**true**;  
15.             **return** **true**;      
16.         \}  
17.     \}      
18.     **return** **false**;  
19. \}  
20. **int** main()\{  
21.     memset(a,0,**sizeof**(a));  
22.     memset(vis,0,**sizeof**(vis));  
23.     swi=**false**;  
24.     scanf("%d %d",&n,&c);  
25.     **int** r1,r2;  
26.     **for**(**int** i=0;i<c;++i)\{  
27.         scanf("%d %d",&r1,&r2);  
28.         a\[r1\]\[r2\]=1;  
29.     \}  
30.     dfs(1);  
31.     **if**(!swi) printf("NO\\n");  
32. \}  
33.

[view plain]: http://blog.csdn.net/panhe1992/article/details/8366466#