2020-04-26

AtCoder ABC 146 D - Coloring Edges on Tree (緑色, 400 点)

軽めの構築問題！！
今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう！

問題へのリンク

問題概要

$N$ 頂点の木が与えられる。

$N-1$ 本の辺に対して、なるべく少ない種類の色を用いて色を塗っていきたい。ただし、どの頂点についても、隣接している辺の色がすべて互いに相異なるようにする必要がある。

そのような塗り分け型を実現できるような色の種類の最小値を求め、具体的な塗り分け方を一つ与えよ。

制約

$2 \le N \le 10^{5}$

考えたこと

誰もが直感的に思うかもしれない。

次数 (つながる辺の本数) が最大の頂点がボトルネックになる
次数の最大値を d とすると、d 色で塗り分けられそう

もし「具体的な塗り分け方を求めよ」と言われなければ、最大次数を出力してしまって良さそう。でも今回は、具体的な塗り方を求めることも要求されている。それは証明も込みで要求されているのに等しい。

木なので

今回は一般のグラフではないので割と考えやすい。ちなみに今回の問題、一般のグラフの場合は最大次数色では塗りきれないケースが存在する (最大次数色 + 1 で塗ることは可能)！！！！

それはさておき、木を扱うときに定番となる考え方は「根を一つテキトーに決めてしまう」というのがある。これをすると木の頂点にある種の順序付けができるのだ。下図の左側のグラフで青い矢印で示したように、頂点を 1 つ選んで根にすると、右側のグラフのような根付き木になる。

そうすると、根頂点から順番に、その隣接辺の色を決めていけば良さそうに思えてくる (DFS でも BFS でもよい)。ここで注目したいのは

新たな頂点について、その隣接辺たちに色を塗ろうとするとき
その隣接辺たちのうち、すでに色が塗られてしまっているのは一本だけ

ということだ。その一本というのは「親頂点」に他ならない。よって、その一色を避けるように色付けすればよいだけだ。

DFS でも BFS でも

木の探索の仕方は、DFS でも BFS でもどちらでもいい。重要なことは、根付きにおいて、どの 2 つの頂点 u, v についても、

u が v の先祖 (v が u の子孫) であるとき
u が先に処理されていて、その後 v を処理する

という風にすることだ。計算量はいずれにしても $O(N)$ となる。

DFS による実装

DFS を用いて木を走査する方法自体は、以下の記事などを参照に。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Edge = pair<int,int>; // (隣接頂点, 辺番号)
using Graph = vector<vector<Edge>>;
int N;
Graph G;

// v: 頂点、p: 親、pc: 親から来た辺の色、res: 色
void dfs(int v, int p, int pc, vector<int> &res) {
    int color = 1;
    if (color == pc) ++color;
    for (auto e : G[v]) {
        if (e.first == p) continue; // 逆流しない
        res[e.second] = color;
        dfs(e.first, v, color, res);
        ++color;
        if (color == pc) ++color;
    }
}

int main() {
    cin >> N;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].emplace_back(b, i); 
        G[b].emplace_back(a, i);
    }
    int max_color = 0;
    for (int i = 0; i < N; ++i) chmax(max_color, (int)G[i].size());
    vector<int> res(N-1, -1);
    dfs(0, -1, -1, res);
    cout << max_color << endl;
    for (auto v : res) cout << v << endl;
}

BFS による実装

BFS の実装方法自体は以下の記事などを参考に。

BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Edge = pair<int,int>; // (隣接頂点, 辺番号)
using Graph = vector<vector<Edge>>;
int N;
Graph G;

int main() {
    cin >> N;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].emplace_back(b, i); 
        G[b].emplace_back(a, i);
    }
    int max_color = 0;
    for (int i = 0; i < N; ++i) chmax(max_color, (int)G[i].size());
    vector<int> res(N-1, -1);

    vector<int> dist(N, -1);
    queue<pair<int,int>> que; // (頂点, 前回の色)
    que.push({0, -1});
    dist[0] = 0;
    while (!que.empty()) {
        auto p = que.front(); que.pop();
        int v = p.first, c = p.second;
        int color = 1;
        if (color == c) ++color;
        for (auto e : G[v]) {
            if (dist[e.first] == -1) {
                dist[e.first] = dist[v] + 1;
                que.push({e.first, color});
                res[e.second] = color;
                ++color;
                if (color == c) ++color;
            }
        }
    }
    cout << max_color << endl;
    for (auto v : res) cout << v << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます