SHARE
TWEET

Untitled

a guest Feb 17th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. struct vert
  8. {
  9.     int visited = 0;
  10.     vector<int> points;
  11.     int dist = 0;
  12. };
  13.  
  14. void BFS(vector<vert> &V, int Start)
  15. {
  16.     V[Start].visited = 1;
  17.      
  18.     queue<int> Q;
  19.     Q.push(Start);
  20.  
  21.     while (!Q.empty())
  22.     {
  23.         int U = Q.front();
  24.         Q.pop();
  25.          
  26.         for (int i = 0; i < V[U].points.size(); ++i)
  27.             if (V[V[U].points[i]].visited == 0)
  28.             {
  29.                 V[V[U].points[i]].visited = 1;
  30.                 V[V[U].points[i]].dist = V[U].dist + 1;
  31.                 Q.push(V[U].points[i]);
  32.             }
  33.          
  34.         V[U].visited = 2;
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40.     ifstream fin("pathbge1.in");
  41.     ofstream fout("pathbge1.out");
  42.     
  43.     int N, M, S, E;
  44.     fin >> N >> M;
  45.     vector<vert> V(N);
  46.      
  47.     for (int i = 0; i < M; ++i)
  48.     {
  49.         fin >> S >> E;
  50.          
  51.         V[S - 1].points.push_back(E - 1);
  52.         V[E - 1].points.push_back(S - 1);
  53.     }
  54.      
  55.     BFS(V, 0);
  56.      
  57.     for (int i = 0; i < N; ++i)
  58.         fout << V[i].dist << " ";
  59.     
  60.     return 0;
  61. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top