Advertisement
ainem

BFS

Aug 12th, 2021 (edited)
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. /*    Never let anyone dull your sparkle...    */
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // type definition
  6. #define int long long
  7. using i64 = int64_t;
  8. typedef pair<int, int> ii;
  9. // constants
  10. constexpr int N = 1e5 + 2;
  11. constexpr int INF = 0x3f3f3f3f;
  12. constexpr int MOD = 1e9 + 7;
  13. constexpr float PI = 3.14;
  14. // possible moves
  15. constexpr int dx[8] = {1, 1, -1, -1, 0, 0, 1, -1};
  16. constexpr int dy[8] = {1, 0, -1, 0, 1, -1, -1, 1};
  17. // shortcuts
  18. #define pb push_back
  19. #define eb emplace_back
  20. #define mp make_pair
  21. #define fi first
  22. #define se second
  23. #define endl '\n'
  24. #define sz(x) i64(x.size())
  25. #define all(x) begin(x), end(x)
  26. #define rall(x) begin(x), end(x), greater<int>()
  27. // loop definition
  28. #define FOR(i, n, m) for (int i = n; i <= m; ++i)
  29. #define FORD(i, n, m) for (int i = n; i >= m; --i)
  30.  
  31. vector<int> g[N];
  32. queue<int> q;
  33. bool used[N];
  34. int d[N], parent[N];
  35. int n, m;
  36.  
  37. void BFS(int s) {
  38.     q.push(s);
  39.     used[s] = true;
  40.     parent[s] = -1;
  41.     while (!q.empty()) {
  42.         int u = q.front();
  43.         q.pop();
  44.         for (int v : g[u]) {
  45.             if (!used[v]) {
  46.                 used[v] = true;
  47.                 q.push(v);
  48.                 d[v] = d[u] + 1;
  49.                 parent[v] = u;
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. void PATH(int t) {
  56.     if (!used[t])
  57.         cout << "No path!" << endl;
  58.     else {
  59.         vector<int> path;
  60.         for (int i = t; i != -1; i = parent[i]) path.pb(i);
  61.         reverse(all(path));
  62.         for (int i : path) cout << i << ' ';
  63.     }
  64. }
  65. int32_t main(void) {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.  
  69.     //freopen("main.INP", "r", stdin);
  70.     //freopen("main.OUT", "w", stdout);
  71.  
  72.     cin >> n >> m;
  73.     int S, T; cin >> S >> T;
  74.     while (m--) {
  75.         int x, y; cin >> x >> y;
  76.         g[x].pb(y);
  77.         g[y].pb(x);
  78.     }
  79.  
  80.     BFS(S);
  81.     cout << d[T] << endl;
  82.     PATH(T);
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement