http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2139
BFS 借助队列 将节点的邻接点依次存入队中
View Code
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include<string.h> 4 int k[1001][1001],f[1001],n,m,p = 0,w; 5 typedef struct node 6 { 7 int num,y; 8 }st; 9 st q[1001]; 10 void inque(int x) 11 { 12 p++; 13 q[p].y = x; 14 f[x] = 1; 15 } 16 int main() 17 { 18 int i,j,a,b; 19 while(scanf("%d%d", &n, &m)!=EOF) 20 { 21 memset(k,0,sizeof(k)); 22 memset(f,0,sizeof(f)); 23 memset(q,0,sizeof(q)); 24 p = 0; 25 int flag = 0; 26 for(i = 1 ; i <= m ; i++) 27 { 28 scanf("%d%d", &a, &b); 29 k[a][b] = 1; 30 } 31 inque(n); 32 q[p].num = 0; 33 w = 0; 34 do 35 { 36 w++; 37 for(i = 1 ; i <= n ; i++) 38 { 39 if(k[q[w].y][i] == 1&&f[i] == 0) 40 { 41 inque(i); 42 q[p].num = q[w].num+1; 43 if(i == 1) 44 { 45 flag = 1; 46 break; 47 } 48 } 49 } 50 if(flag == 1) 51 break; 52 }while(p!=w); 53 if(flag == 1) 54 printf("%d\n",q[p].num); 55 else 56 printf("NO\n"); 57 } 58 return 0; 59 }