Read-Graph (グラフ入力)
(src/graph/Read-Graph.hpp)

• View this file on GitHub
• Last update: 2022-10-26 15:07:24+09:00
• Include: #include "src/graph/Read-Graph.hpp"

概要

std::vector<std::vector<int>> read_graph(int n, int m, bool undirect = true, bool minus = true)

グラフを隣接リスト表現で受け取ります

機能

• n: 頂点数
• m: 辺数
• undirect: 無向グラフか否か（デフォルトでtrue)
• minus: 1-indexedか否か(デフォルトでtrue)

• 返り値: std::vector<std::vector<int>>

• read_tree: $m = n - 1$ のread_graphを呼び出します。(つまり木)

Verified with

• test/ABC282-D.test.cpp
• test/ABC284-C.test.cpp
• test/Read-Graph-AtCoder.test.cpp
• test/Read-Graph.test.cpp
• test/simple-bfs2.test.cpp

Code

#pragma once

#include <vector>
#include <iostream>

namespace zawa {

std::vector<std::vector<int>> read_graph(int n, int m, bool undirect = true, bool minus = true) {
    std::vector<std::vector<int>> res(n, std::vector(0, 0));
    for (int _ = 0 ; _ < m ; _++) {
        int u, v;
        std::cin >> u >> v;
        res[u - minus].emplace_back(v - minus);
        if (undirect) {
            res[v - minus].emplace_back(u - minus);
        }
    }
    return res;
}

std::vector<std::vector<int>> read_tree(int n, bool undirect = true, bool minus = true) {
    return read_graph(n, n - 1, undirect, minus);
}

}

#line 2 "src/graph/Read-Graph.hpp"

#include <vector>
#include <iostream>

namespace zawa {

std::vector<std::vector<int>> read_graph(int n, int m, bool undirect = true, bool minus = true) {
    std::vector<std::vector<int>> res(n, std::vector(0, 0));
    for (int _ = 0 ; _ < m ; _++) {
        int u, v;
        std::cin >> u >> v;
        res[u - minus].emplace_back(v - minus);
        if (undirect) {
            res[v - minus].emplace_back(u - minus);
        }
    }
    return res;
}

std::vector<std::vector<int>> read_tree(int n, bool undirect = true, bool minus = true) {
    return read_graph(n, n - 1, undirect, minus);
}

}

Back to top page