test/BFS.test.cpp

• View this file on GitHub
• Last update: 2022-11-13 19:29:53+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_C

Depends on

• BFS (幅優先探索) (src/graph/BFS.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_C"

#include "../src/graph/BFS.hpp"

#include <iostream>

int main() {
    int n; std::cin >> n;
    zawa::BFS bfs(n);
    for (int _ = 0 ; _ < n ; _++) {
        int u; std::cin >> u;
        int k; std::cin >> k;
        for (int __ = 0 ; __ < k ; __++) {
            int v; std::cin >> v;
            bfs.add_edge(u - 1, v - 1);
        }
    }
    bfs.build(0);
    for (int i = 0 ; i < n ; i++) {
        int ans = bfs.get_dist(i);
        std::cout << i + 1 << ' ' << (ans == bfs.inf() ? -1 : ans) << std::endl;
    }
}

#line 1 "test/BFS.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_C"

#line 2 "src/graph/BFS.hpp"

#include <queue>
#include <vector>
#include <limits>
#include <utility>

namespace zawa {

class BFS {
public:

    BFS(std::size_t n)
        : G(n)
        , dist(n, _inf)
        , prevs(n, -1)
        , route(n, -1) {}

    int add_edge(int from, int to) {
        int res = (int)edges.size();
        edges.push_back({ from, to });
        G[from].emplace_back(res);
        return res;
    }

    std::pair<int, int> get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        dist[s] = 0;
        std::queue<int> que({ s });
        while (que.size()) {
            int v = que.front();
            que.pop();
            for (auto x : G[v]) {
                auto [_, t] = edges[x];
                if (dist[t] > dist[v] + 1) {
                    dist[t] = dist[v] + 1;
                    prevs[t] = v;
                    route[t] = x;
                    que.emplace(t);
                }
            }
        }
    }

    int inf() {
        return _inf;
    }

    int get_dist(int v) {
        return dist[v];
    }

    int get_prev(int v) {
        return prevs[v];
    }

    int get_route(int v) {
        return route[v];
    }

private:
    static constexpr int _inf = std::numeric_limits<int>::max();
    std::vector<std::pair<int, int>> edges;
    std::vector<std::vector<int>> G;
    std::vector<int> dist;
    std::vector<int> prevs;
    std::vector<int> route;
};

}// namespace zawa
#line 4 "test/BFS.test.cpp"

#include <iostream>

int main() {
    int n; std::cin >> n;
    zawa::BFS bfs(n);
    for (int _ = 0 ; _ < n ; _++) {
        int u; std::cin >> u;
        int k; std::cin >> k;
        for (int __ = 0 ; __ < k ; __++) {
            int v; std::cin >> v;
            bfs.add_edge(u - 1, v - 1);
        }
    }
    bfs.build(0);
    for (int i = 0 ; i < n ; i++) {
        int ans = bfs.get_dist(i);
        std::cout << i + 1 << ' ' << (ans == bfs.inf() ? -1 : ans) << std::endl;
    }
}

Back to top page