sdut2138图结构练习——BFSDFS—

sdut2138图结构练习——BFSDFS——判断可达性

刚开始把路径标记给取消了就一直TLE

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include<string.h>
 4 int k[1001][1001],f[1001],n,m,a,b,flag,x;
 5 void dfs(int x)
 6 {
 7     int j;
 8     f[x] = 1;
 9     if(flag == 1)
10     return ;
11     for(j = n ;j>=1 ; j-- )
12         if(k[x][j] == 1&&f[j] == 0)
13         {
14             if(j == 1)
15             {
16                 flag = 1;
17                 return;
18             }
19             dfs(j);
20         }
21 }
22 int main()
23 {
24     int i, j;
25     while(scanf("%d%d", &n, &m)!=EOF)
26     {
27         memset(k, 0, sizeof(k));
28         memset(f, 0, sizeof(f));
29         flag = 0;
30         for(i = 1 ; i <= m ; i++)
31         {
32             scanf("%d%d", &a, &b);
33             k[a][b] = 1;
34         }
35         dfs(n);
36         if(flag)
37         printf("YES\n");
38         else
39         printf("NO\n");
40     }
41     return 0;
42 }