2138=数据结构实验之图论三：判断可达性

 1 #include <stdio.h>
 2 #include <string.h>
 3 int map[1000][1000];
 4 int visit[1000];
 5 int n;
 6 int max;//利用max来标记是否达到隘口1，如达到则max=1；
 7 void DFS(int t)
 8 {
 9     visit[t]=1;
10     int i;
11     for(i=n; i>=0; i--) //从n开始出发。
12     {
13         if(map[t][i]==1&&visit[i]==0)
14         {
15             if(i==1)
16             {
17                 max=1;    //若i=1，则表示能够到达。
18                 return;
19             }
20             DFS(i);
21         }
22     }
23 }
24 int main()
25 {
26     int m;
27     while(~scanf("%d %d",&n,&m))
28     {
29         int i,a,b;
30         max=0;
31         memset(map,0,sizeof(map));
32         memset(visit,0,sizeof(visit));
33         for(i=0; i<m; i++)
34         {
35             scanf("%d %d",&a,&b);
36             map[a][b]=1;//此题路线是单向。
37         }
38         DFS(n);//因为天灾军团在n隘口，所以从n隘口出发。
39         if(max==1)printf("YES
");
40         else printf("NO
");
41     }
42     return 0;
43 }