[AtCoder] ABC146 D – Coloring Edges on Tree (400点)

2019年11月30日AtCoderグラフ,木,400点,BFS,辺彩色

問題

木構造について、頂点から見た時に自身から伸びる枝に重複が無いように色を塗る。使う色の数の最小値はいくつか？

問題：D – Coloring Edges on Tree

(木構造はグラフの一種と捉えられるので、グラフの辺彩色と言うこともあります。)

解法

どの頂点からでも、使う色が最小になるように幅優先探索をしながら枝を彩色していくと、使う色の数が最小になります。

注意点

頂点数はNですが、最大値は\(10^5\)となっています。グラフを隣接行列で表現しようとすると、\(10^{10}\)に比例したメモリを使用することになります。int型で保持するなら1Bのデータが\(10^{10}\)個必要なので、10GBのメモリが必要になってしまいます。

このような場合は隣接リスト表現を用いると良いでしょう。

（隣接行列や隣接リスト行列についてはグラフを参照のこと）

プログラム例

C++での例

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

int main() {
    int N;
    cin >> N;

    vector<vector<int>> G(N);    // 隣接リスト表現によるグラフ
    vector<pair<int, int>> E_in; // 辺の入力の順番を保持する

    for (int i = 1; i < N; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
        pair<int, int> p = make_pair(a, b);
        E_in.emplace_back(p);
    }

    queue<int> que;
    vector<int> used(N, 0);
    vector<int> parent(N, 0); // 親との間にある辺の数値
    int max_color = 0;
    map<pair<int, int>, int> E_num; // 辺への割り振った番号を保持する
    que.emplace(0); // 最初のものは何でも良いので0からにする
    used[0] = 1;
    while (que.size() != 0) {
        int state = que.front(); // 現在の状態

        que.pop();
        int color_num = 0;
        for (auto next : G[state]) {
            if (used[next] != 1) {
                color_num++;
                used[next] = 1;
                if (color_num == parent[state]) {
                    // 親との間にある辺と番号が被らないようにする
                    color_num++;
                }
                pair<int, int> p = make_pair(state, next);
                E_num[p] = color_num; //辺彩色
                parent[next] = color_num;
                que.push(next); //次の状態をqueueへ格納
            }
        }
        max_color = max(max_color, color_num);
    }

    cout << max_color << "\n";
    for (auto i : E_in) {
        cout << E_num[i] << "\n";
    }

    return 0;
}

AtCoderグラフ,木,400点,BFS,辺彩色