图练习-BFS-从起点到目标点的最短步数

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2830

简单bfs

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int N=;

 int head[N],vis[N];

 int cnt = ;

 struct Edge

 {

     int u,v;

     int next;

 } edge[*N];

 struct node

 {

     int x,step;

     node(int x,int step):x(x),step(step) {}

 };

 void add(int u,int v)

 {

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].next = head[u];

     head[u] = cnt++;

 }

 int bfs(int n)

 {

     memset(vis,,sizeof(vis));

     queue<node>q;

     node s(n,);

     q.push(s);

     vis[n] = ;

     while(!q.empty())

     {

         node u = q.front();

         q.pop();

         if (u.x==)

             return u.step;

         for (int j = head[u.x]; j!=-; j=edge[j].next)

         {

             int v = edge[j].v;

             if (!vis[v])

             {

                 q.push(node(v,u.step+));

                 vis[v] = ;

             }

         }

     }

     return -;

 }

 int main()

 {

     int n,m;

     int u,v;

     while(~scanf("%d%d",&n,&m))

     {

         cnt = ;

         memset(vis,,sizeof(vis));

         memset(head,-,sizeof(head));

         for (int i = ; i < m; i++)

         {

             scanf("%d%d",&u,&v);

             add(u,v);

             add(v,u);

         }

         int ans = bfs(n);

         if (ans==-)

             puts("NO");

         else

             printf("%d\n",ans);

     }

     return ;

 }