test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp

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

#include <iostream>
#include <vector>

#include "../../Graph/graph-template.hpp"
#include "../../Graph/Shortest-Path/bfs.hpp"

#include "../../Util/IO/var-declaration-with-input.hpp"
#include "../../Util/IO/println.hpp"

int main() {
    var(int, N);

    Graph<void> G(N);
    for (int i = 0; i < N; ++i) {
        var(int, u, k);
        --u;
        while (k--) {
            var(int, v);
            --v;
            G[u].emplace_back(v);
        }
    }

    std::vector<int> dist(N, -1);
    bfs(dist, 0, [&](int v, auto push) {
        for (const int to : G[v]) push(to);
    });

    for (int i = 0; i < N; ++i) {
        println(i + 1, dist[i]);
    }

    return 0;
}

#line 1 "test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C"

#include <iostream>
#include <vector>

#line 2 "Graph/graph-template.hpp"
#include <cstdint>
#line 5 "Graph/graph-template.hpp"

/**
 * @brief graph-template (Edge, Graph, MatrixGraph)
 */
//! グラフの辺 (重み付き)
template <class T>
struct Edge {
    int from, to;
    T weight;
    int id;

    Edge() = default;

    constexpr explicit Edge(int to_, const T& weight_)
        : Edge(-1, to_, weight_, -1) {}

    constexpr Edge(int from_, int to_, const T& weight_, int id_ = -1)
        : from(from_)
        , to(to_)
        , weight(weight_)
        , id(id_) {}

    constexpr const Edge rev() const { return Edge(to, from, weight, id); }

    template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr>
    constexpr operator Int() const {
        return static_cast<Int>(to);
    }

    friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to >> e.weight; }
};

//! グラフの辺 (重みなし)
template <>
struct Edge<void> {
    int from, to;
    int id;

    Edge() = default;

    constexpr explicit Edge(int to_)
        : Edge(-1, to_, -1) {}

    constexpr Edge(int from_, int to_, int id_ = -1)
        : from(from_)
        , to(to_)
        , id(id_) {}

    constexpr const Edge rev() const { return Edge(to, from, id); }

    template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr>
    constexpr operator Int() const {
        return static_cast<Int>(to);
    }

    friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to; }
};

template <class T>
using Graph = std::vector<std::vector<Edge<T>>>;
#line 2 "Graph/Shortest-Path/bfs.hpp"
#include <cassert>
#include <functional>
#include <queue>
#include <utility>
#line 7 "Graph/Shortest-Path/bfs.hpp"

#line 2 "Util/at.hpp"
#include <tuple>
#line 4 "Util/at.hpp"
#include <type_traits>

/**
 * @brief at() ()
 */
namespace arumakan {

//! at(a, i) returns a[i]
template <class Array, class Integer, std::enable_if_t<std::is_integral<Integer>::value, std::nullptr_t> = nullptr>
inline auto at(Array&& a, Integer i) -> decltype(a[0])& {
    return a[i];
}

//! at(a, Tuple{i}) returns a[i]
template <class Array, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 1, std::nullptr_t> = nullptr>
inline auto at(Array&& a, Tuple index) -> decltype(a[0])& {
    return a[std::get<0>(index)];
}

//! at(mat, Tuple{y, x}) returns mat[y][x]
template <class Matrix, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 2, std::nullptr_t> = nullptr>
inline auto at(Matrix&& mat, Tuple index) -> decltype(mat[0][0])& {
    return mat[std::get<0>(index)][std::get<1>(index)];
}

//! at(cube, Tuple{z, y, x}) returns cube[z][y][x]
template <class Cube, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 3, std::nullptr_t> = nullptr>
inline auto at(Cube&& cube, Tuple index) -> decltype(cube[0][0][0])& {
    return cube[std::get<0>(index)][std::get<1>(index)][std::get<2>(index)];
}

}  // namespace arumakan
#line 3 "Util/int-infinity.hpp"

/**
 * @brief int-infinity (整数のデカイ値)
 * 2倍してもオーバーフローしない & memset()にも使える (需要ある？)
 */
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
#line 10 "Graph/Shortest-Path/bfs.hpp"

/**
 * @brief bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応)
 *
 * @param dist:
 *      start からの距離を格納する配列。
 *      要素数は頂点数以上でなければならない。-1やINFなど、距離として正当でない値でfillされている必要がある。
 *      多次元配列でもOK。
 *
 * @param start:
 *      頂点を表すdistの添字。
 *      distが一次元配列なら整数型,
 *      distが二次元配列ならstd::pair<integer, integer> または std::tuple<integer, integer> または std::array<integer, 2>,
 *      distが三次元配列ならstd::tuple<integer, integer, integer> または std::array<integer, 3>。
 *      start = {i, j, k} のとき dist[i][j][k] でアクセスする。
 *
 * @param enumerateNextVertex:
 *      fn(from: Vertex, fn(to: Vertex) => void) => void
 *      第一引数にVertex, 第二引数に関数をとる関数。
 *      この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで bfs() に遷移処理を委譲する。
 */
template <class DistArray, class Vertex, class NextVertexEnumerator>
DistArray bfs(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) {
    using arumakan::at;
    assert(!dist.empty());
    assert(at(dist, start) == -1 || at(dist, start) >= INF);

    std::queue<Vertex> que({start});
    const auto yetReachedMarker = at(dist, start);
    at(dist, start) = 0;
    while (!que.empty()) {
        const Vertex v = std::move(que.front());
        que.pop();
        const auto curDist = at(dist, v);
        enumerateNextVertex(v, [&](Vertex nxt) {
            if (at(dist, nxt) == yetReachedMarker) {
                at(dist, nxt) = curDist + 1;
                que.push(nxt);
            }
        });
    }
    return dist;
}
#line 8 "test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp"

#line 3 "Util/IO/var-declaration-with-input.hpp"

/**
 * @brief 複数変数宣言をして同時に入力もするやつ
 */
template <class T>
std::istream& operator,(std::istream& is, T& rhs) {
    return is >> rhs;
}

#define var(type, ...) \
    type __VA_ARGS__;  \
    std::cin >> __VA_ARGS__
#line 4 "Util/IO/println.hpp"

/**
 * @brief println() (可変個の値を空白区切りで出力して改行する)
 */
inline void println() {
    std::cout << '\n';
}
template <class Head, class... Tail>
inline void println(Head&& head, Tail&&... tail) {
    std::cout << head << &" "[!sizeof...(tail)];
    println(std::forward<Tail>(tail)...);
}
#line 11 "test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp"

int main() {
    var(int, N);

    Graph<void> G(N);
    for (int i = 0; i < N; ++i) {
        var(int, u, k);
        --u;
        while (k--) {
            var(int, v);
            --v;
            G[u].emplace_back(v);
        }
    }

    std::vector<int> dist(N, -1);
    bfs(dist, 0, [&](int v, auto push) {
        for (const int to : G[v]) push(to);
    });

    for (int i = 0; i < N; ++i) {
        println(i + 1, dist[i]);
    }

    return 0;
}