算法基础之图中点的层次

图中点的层次

• 核心思想：BFS 树与图的广度优先遍历

  •   #include<iostream>
      #include<cstring>
      #include<algorithm>
      #include<queue>
      
      using namespace std;
      
      const int N=100010;
      int n,m;
      int d[N];  //距离
      int idx,e[N],ne[N],h[N];
      
      
      void add(int a, int b)
      {
          e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;  //跟树的重心一样
      }
      
      int bfs(){
          memset(d, -1, sizeof d);
          d[1] = 0;
          queue<int> q;  //初始化
          q.push(1);
          
          while(q.size())
          {
              int t=q.front();
              q.pop();
              
              for(int i=h[t];i!=-1;i=ne[i])
              {
                  int j=e[i];
                  if(d[j] == -1)
                  {
                      d[j] = d[t] +1;
                      q.push(j);
                  }
              }
          }
          
          return d[n];
      }
      
      int main(){
          cin>>n>>m;
          
          memset(h, -1, sizeof h);
          
          while(m--){
              int a,b;
              cin>>a>>b;
              add(a,b);
          }
          
          cout<<bfs()<<endl;
          
          return 0;
      }