test/simple-bfs1.test.cpp

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

Depends on

• bfs (simple ver) (src/graph/simple/bfs.hpp)

Code

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

#include "../src/graph/simple/bfs.hpp"

#include <iostream>

int main() {
    int n; std::cin >> n;
    std::vector G(n, std::vector(0, 0));
    for (int _ = 0 ; _ < n ; _++) {
        int id; std::cin >> id;
        int k; std::cin >> k;
        for (int __ = 0 ; __ < k ; __++) {
            int v; std::cin >> v;
            G[id - 1].push_back(v - 1);
        }
    }
    const int inf = 1e9;
    auto table = zawa::bfs(G, 0, inf);
    for (int i = 0 ; i < n ; i++) {
        std::cout << i + 1 << ' ';
        std::cout << (table[i] == inf ? -1 : table[i]) << std::endl;
    }
}

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

#line 2 "src/graph/simple/bfs.hpp"

#include <vector>
#include <queue>

namespace zawa {

std::vector<int> bfs(const std::vector<std::vector<int>>& G, int s, int inf = 2e9) {
    std::vector<int> res(G.size(), inf);
    res[s] = 0;
    std::queue<int> que({ s });
    while (que.size()) {
        int v = que.front();
        que.pop();
        for (auto x : G[v]) {
            if (res[x] > res[v] + 1) {
                res[x] = res[v] + 1;
                que.push(x);
            }
        }
    }
    return res;
}

} // namespace zawa
#line 4 "test/simple-bfs1.test.cpp"

#include <iostream>

int main() {
    int n; std::cin >> n;
    std::vector G(n, std::vector(0, 0));
    for (int _ = 0 ; _ < n ; _++) {
        int id; std::cin >> id;
        int k; std::cin >> k;
        for (int __ = 0 ; __ < k ; __++) {
            int v; std::cin >> v;
            G[id - 1].push_back(v - 1);
        }
    }
    const int inf = 1e9;
    auto table = zawa::bfs(G, 0, inf);
    for (int i = 0 ; i < n ; i++) {
        std::cout << i + 1 << ' ';
        std::cout << (table[i] == inf ? -1 : table[i]) << std::endl;
    }
}

Back to top page