Advertisement
Mirbek

Путь в графе

Dec 23rd, 2021
1,015
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 5;
  6.  
  7. int n, m, cycle = 0;
  8. int used[N], dist[N];
  9. vector <int> g[N];
  10.  
  11. int main() {
  12.     cin >> n;
  13.    
  14.     for (int i = 1; i <= n; i++) {
  15.         for (int j = 1; j <= n; j++) {
  16.             int x;
  17.             cin >> x;
  18.             if (x == 1) {
  19.                 g[i].push_back(j);
  20.             }
  21.         }
  22.     }
  23.    
  24.     int f, s;
  25.     cin >> f >> s;
  26.  
  27.     if (f == s) {
  28.     cout << 0 << endl;
  29.     return 0;
  30.     }
  31.  
  32.     queue <int> q;
  33.     q.push(f);
  34.     dist[f] = 0;
  35.     used[f] = 1;
  36.    
  37.     while (!q.empty()) {
  38.         int v = q.front();
  39.         q.pop();
  40.         for (int i = 0; i < g[v].size(); i++) {
  41.             int to = g[v][i];
  42.             if (!used[to]) {
  43.                 used[to] = 1;
  44.                 dist[to] = dist[v] + 1;
  45.                 q.push(to);
  46.             }
  47.         }
  48.     }
  49.    
  50.     if (dist[s] == 0) {
  51.         cout << -1;
  52.     return 0;
  53.     }
  54.  
  55.     cout << dist[s] << endl;
  56.     vector <int> path;
  57.     while (dist[s] > 0) {
  58.         path.push_back(s);
  59.         for (int i = 0; i < g[s].size(); i++) {
  60.             int to = g[s][i];
  61.             if (dist[s] - 1 == dist[to]) {
  62.                 s = to;
  63.                 break;
  64.             }
  65.         }
  66.     }
  67.    
  68.     path.push_back(s);
  69.     reverse(path.begin(), path.end());
  70.    
  71.     for (int x : path) {
  72.         cout << x << " ";
  73.     }
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement