[AtCoder] ABC 146 D – Coloring Edges on Tree

2019年12月20日

問題

方針

必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int a[N- 1], b[N - 1];
    vector<int> adj[N];
    int d[N]{};
    for (int i = 0; i < N - 1; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        d[a[i]]++;
        d[b[i]]++;
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    int l = 0;
    for (int i : d) {
        l = max(l, i);
    }
    int c[N];
    fill(c, c + N, -1);
    deque<int> q;
    q.push_back(0);
    int vis[N]{};
    vis[0] = 1;
    map<int, int> m[N];
    set<int> s[N];
    map<string, int> t;
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        int k = 1;
        for (int j = 0; j < adj[u].size(); j++) {
            int v = adj[u][j];
            if (m[u].count(v) == 0 && m[v].count(u) == 0) {
                while (s[u].count(k) != 0 || s[v].count(k) != 0) {
                    k++;
                }
                m[u][v] = k;
                m[v][u] = k;
                s[u].insert(k);
                s[v].insert(k);
            }
            if (vis[v] == 0) {
                vis[v] = 1;
                q.push_back(v);
            }
        }
    }
    cout << l << "\n";
    for (int i = 0; i < N - 1; i++) {
        cout << m[a[i]][b[i]] << "\n";
    }
    return 0;
}