Graph/tests/aizu_alds1_11_c_bfs.test.cpp

• View this file on GitHub
• Last update: 2022-12-14 02:22:04+08:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C

Depends on

• Graph/bfs.h

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C"

#include <bits/stdc++.h>
using namespace std;

#include "../bfs.h"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    Graph g(n);

    REP(i,n) {
        int u, k; cin >> u >> k;
        --u;
        while (k--) {
            int v; cin >> v;
            --v;
            g.add_edge(u, v);
        }
    }
    auto dist = g.bfs(0);
    REP(i,n) {
        cout << (i+1) << ' ' << dist[i] << '\n';
    }
    return 0;
}

#line 1 "Graph/tests/aizu_alds1_11_c_bfs.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C"

#include <bits/stdc++.h>
using namespace std;

#line 1 "Graph/bfs.h"
// BFS {{{
// - Index from 0
// - Directed
// - Supports multi-source BFS
// - Supports reconstruct path
//
// Tested:
// - https://oj.vnoi.info/problem/vmunch
// - https://oj.vnoi.info/problem/vcoldwat
// - (trace) https://cses.fi/problemset/task/1667/
// - (multi-source) https://cses.fi/problemset/task/1193/
struct Graph {
    Graph(int _n) : n(_n), g(n) {}

    void add_edge(int u, int v, bool bi_directional = false) {
        g[u].push_back(v);
        if (bi_directional) g[v].push_back(u);
    }

    // return
    // - shortest distance from start -> target
    // - path
    // If no path -> returns -1
    pair<int, vector<int>> bfs(int start, int target) const {
        assert(0 <= start && start < n);
        assert(0 <= target && target < n);

        auto [dist, trace] = _bfs({start}, target);
        if (dist[target] < 0) {
            return {dist[target], {}};
        }
        vector<int> path;
        for (int u = target; u != start; u = trace[u]) {
            path.push_back(u);
        }
        path.push_back(start);
        reverse(path.begin(), path.end());
        return {dist[target], path};
    }

    // return: dist: vector<int>, dist[u] = shortest distance from start -> u
    vector<int> bfs(int start) const {
        assert(0 <= start && start < n);
        return _bfs({start}, -1).first;
    }

    // multi-source BFS
    // Return: dist[u] = shortest distance from any source -> u
    vector<int> bfs(vector<int> starts) const {
        return _bfs(starts, -1).first;
    }

// private:

    // Start BFS from start, and stop when reaching target.
    // Target = -1 -> BFS whole graph
    // Returns {distance, trace}
    pair<vector<int>, vector<int>> _bfs(vector<int> starts, int target) const {
        assert(-1 <= target && target < n);

        queue<int> qu;
        vector<int> dist(g.size(), -1);
        vector<int> trace(g.size(), -1);

        for (int start : starts) {
            assert(0 <= start && start < n);
            dist[start] = 0;
            qu.push(start);
        }

        while (!qu.empty()) {
            auto u = qu.front(); qu.pop();
            if (u == target) {
                break;
            }

            for (const auto& v : g[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    trace[v] = u;
                    qu.push(v);
                }
            }
        }

        return {dist, trace};
    }

    int n;
    vector<vector<int>> g;
};
// }}}
#line 7 "Graph/tests/aizu_alds1_11_c_bfs.test.cpp"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    Graph g(n);

    REP(i,n) {
        int u, k; cin >> u >> k;
        --u;
        while (k--) {
            int v; cin >> v;
            --v;
            g.add_edge(u, v);
        }
    }
    auto dist = g.bfs(0);
    REP(i,n) {
        cout << (i+1) << ' ' << dist[i] << '\n';
    }
    return 0;
}

Back to top page