🍣

ABC 146 | D - Coloring Edges on Tree

2020/12/17に公開

競プロ

木

問題

考えたこと

$N$ 頂点の木 $G$ で辺が $N-1$ 個しかないことから閉路をもたない。もし閉路をもっていたら今回のアルゴリズムは使えない。

たとえば以下のような木を考えた時、頂点につながっている辺をすべて別の色で塗るので、4色で塗ることができる。

頂点につながっている辺の個数が最大の色の塗る数である。
塗り方は、とある頂点を決めてそこから各頂点をたどっていきまだ塗られていないところを使ってない色でぬいっていけばいい。

順にやると以下のようになる。

以後同じようにやればいい。

コード

実装時のTips

0-indexedでやると0のインデックスを考慮しなくていい

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// 辺を色分けする
// 辺の数がN-1なので閉路がない
int main() {
  ll n;
  cin >> n;
  int mx = 0;                           // 最大の辺の数
  vector<int> c(n - 1, -1);             // 辺[i]の色(color). -1は色なし
  vector<unordered_set<int>> paths(n);  // 頂点[i]の{辺idx}の集合
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    paths[a].insert(i);
    paths[b].insert(i);
  }
  for (int i = 0; i < n; i++) {
    vector<bool> visit(paths[i].size());  // 色集合. 最大の色数がpaths[i].size()である
    mx = max(mx, (int)paths[i].size());   // 使われる色の最大の数
    // どの色が使われているか確認する
    for (auto idx : paths[i]) {
      if (c[idx] == -1) continue;
      visit[c[idx]] = true;
    }
    // 色が塗られていない辺の色を塗る
    ll vi = 0;
    for (auto v : paths[i]) {
      if (c[v] != -1) continue;
      while (true) {
        if (!visit[vi]) {
          c[v] = vi;
          visit[vi] = true;
          break;
        }
        vi++;
      }
    }
  }
  cout << mx << endl;
  for (int i = 0; i < n - 1; i++) {
    cout << c[i] + 1 << endl;  // 0-indexedなので変換する
  }
}

ABC 146 | D - Coloring Edges on Tree

問題

考えたこと

コード

参考

Discussion