library/graph/shortest_path/BFS.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/graph/shortest_path/BFS.hpp"

Depends on

build/pch/stdc++.hpp

Verified with

test/AOJ/ALDS1_11_C.test.cpp

Code

#pragma once
template <typename GRAPH>
std::pair<std::vector<int>, std::vector<int>> BFS(const GRAPH &g, int s = 0) {
    assert(g.is_prepared());
    std::vector<int> d(g.n, -1), pre(g.n, -1);
    std::queue<int> que;
    d[s] = 0;
    que.push(s);
    while (que.size()) {
        int v = que.front();
        que.pop();
        for (int to : g[v])
            if (d[to] < 0) {
                d[to] = d[v] + 1;
                que.push(to);
            }
    }
    return {d, pre};
}

#line 2 "library/graph/shortest_path/BFS.hpp"
template <typename GRAPH>
std::pair<std::vector<int>, std::vector<int>> BFS(const GRAPH &g, int s = 0) {
    assert(g.is_prepared());
    std::vector<int> d(g.n, -1), pre(g.n, -1);
    std::queue<int> que;
    d[s] = 0;
    que.push(s);
    while (que.size()) {
        int v = que.front();
        que.pop();
        for (int to : g[v])
            if (d[to] < 0) {
                d[to] = d[v] + 1;
                que.push(to);
            }
    }
    return {d, pre};
}