Alex_tz307

BFS-distances

Sep 11th, 2020
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.91 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. ifstream f("bfs.in");
  5. ofstream g("bfs.out");
  6.  
  7. const int NMAX = 100005;
  8. int N, M, S, dist[NMAX];
  9. vector < int > Muchii[NMAX];
  10. queue < int > Q;
  11.  
  12. void BFS()
  13. {
  14.     int nod,vecin;
  15.     while(!Q.empty())
  16.     {
  17.         nod=Q.front();
  18.         Q.pop();
  19.         for(unsigned int i=0;i<Muchii[nod].size();i++)
  20.         {
  21.             vecin=Muchii[nod][i];
  22.             if(dist[vecin]==-1)
  23.             {
  24.                 Q.push(vecin);
  25.                 dist[vecin]=dist[nod]+1;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. void Citire()
  32. {
  33.     f>>N>>M>>S;
  34.     for(int i=1;i<=M;i++)
  35.     {
  36.         int x,y;
  37.         f>>x>>y;
  38.         Muchii[x].push_back(y);
  39.     }
  40. }
  41.  
  42. int main()
  43. {
  44.     Citire();
  45.     for(int i=1;i<=N;i++) dist[i]=-1;
  46.     dist[S]=0;
  47.     Q.push(S);
  48.     BFS();
  49.     for(int i=1;i<=N;i++) g<<dist[i]<<" ";
  50.     f.close();
  51.     g.close();
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment