shortest-path/bfs-restore.hpp

• View this file on GitHub
• Last update: 2020-12-21 18:22:27+09:00
• Include: #include "shortest-path/bfs-restore.hpp"

Verified with

• verify/verify-yuki/yuki-1323.test.cpp

Code

#pragma once

vector<pair<int, int>> bfs_restore(vector<vector<int>>& g, int st = 0) {
  vector<pair<int, int>> d(g.size(), make_pair(-1, -1));
  d[st] = make_pair(0, -1);
  queue<int> Q;
  Q.push(st);
  while (!Q.empty()) {
    int cur = Q.front();
    Q.pop();
    int cd = d[cur].first;
    for (auto&& dst : g[cur]) {
      if (d[dst].first == -1) {
        d[dst].first = cd + 1;
        d[dst].second = cur;
        Q.push(dst);
      }
    }
  }
  return d;
}

#line 2 "shortest-path/bfs-restore.hpp"

vector<pair<int, int>> bfs_restore(vector<vector<int>>& g, int st = 0) {
  vector<pair<int, int>> d(g.size(), make_pair(-1, -1));
  d[st] = make_pair(0, -1);
  queue<int> Q;
  Q.push(st);
  while (!Q.empty()) {
    int cur = Q.front();
    Q.pop();
    int cd = d[cur].first;
    for (auto&& dst : g[cur]) {
      if (d[dst].first == -1) {
        d[dst].first = cd + 1;
        d[dst].second = cur;
        Q.push(dst);
      }
    }
  }
  return d;
}

Back to top page