ulvis.paste.net

Paste Search Dynamic
Recent pastes
path
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void showPath(const vector<int> & p,bool used[] ,int to)
  9. {
  10.     if(!used[to])
  11.     {
  12.         cout << "No path!";
  13.         return;
  14.     }
  15.     vector<int> path;
  16.     for (int v = to; v != -1; v = p[v])
  17.     {
  18.         path.push_back(v);
  19.     }
  20.     reverse(path.begin(), path.end());
  21.     cout << "Path : ";
  22.     for (auto x : path)
  23.     {
  24.         cout << x + 1 << " ";
  25.     }
  26.     cout << "\nNum of edges: ";
  27. }
  28.  
  29. int main()
  30. {
  31.     int n, e; // n - nodes, e - edges
  32.     cin >> n >> e;
  33.     vector<vector<int>> g(n);
  34.     for (size_t i = 0; i < e; i++)
  35.     {
  36.         int from, to;
  37.         cin >> from >> to;
  38.         g[from-1].push_back(to-1);
  39.     }
  40.     int s;
  41.     cin >> s;
  42.     bool used[n] = {0};
  43.     queue<int> q;
  44.     q.push(s-1);
  45.     used[s-1] = true;
  46.     vector<int> d(n), p(n); // d - количество ребер до вершины, p - предок
  47.     while(!(q.empty()))
  48.     {
  49.         int v = q.front();
  50.         q.pop();
  51.         for (size_t i = 0; i < g[v].size(); ++i)
  52.         {
  53.             int to = g[v][i];
  54.             if(!used[to])
  55.             {
  56.                 used[to] = true;
  57.                 q.push(to);
  58.                 d[to] = d[v] + 1;
  59.                 p[to] = v;
  60.             }
  61.         }
  62.     }
  63.     int l;
  64.     cin >> l;
  65.     showPath(p,used, l-1);
  66.  
  67.     return 0;
  68. }
  69.  
Parsed in 0.011 seconds