ABC146 D - Coloring Edges on Tree
April 16, 2020
問題
考えたこと
問題を言い換えると、ある頂点から出る辺の色が全て異なるということ
これより使用する色の最小数は, 一番次数が多い頂点の次数の数と言えそう
色の塗り方を考える
BFSかDFSしていって、ある頂点からでる辺を全て別の色で塗ればいい,
プログラムに落とすことを考えてもう少し詰めると
ある頂点をみるときに, そこから出る辺に対して、色番号を1から順にインクリメントしながらつけていく
そのときに自分の親との間で使った色番号を覚えておき, 親との間で使った色の場合は飛ばしてつけていく
例えばある頂点から出る辺は3つあり, その頂点との親の間では色番号2を使っていた場合
残り2つの辺を見ていき、最初の辺には色番号1をつける
次の辺に色番号2をつけようとしたら、その色は親との間で使ってるので飛ばして、3を使うという感じ
BFSでやった(MLEで落ちる)
DFSあんまうまくかけないので、BFSでやってみたけど失敗した
BFSの場合はqueueで次確認する頂点を突っ込んでいくけど
今回の場合は、親との間で使った色の情報も渡さないといけないので, queue<pair<int, int>>みたいになり,さらに親へ戻らないようにseen配列など用意してってなり複雑になったし、さらに色々配列作りすぎたせいかサイズ大きいテストケースだとMLEが出まくった
ちなみにこんなコード
int main() {
int n; cin >> n;
Graph G(n);
vector<P> input;
rep(i, n-1) {
int a, b; cin >> a >> b;
a--;
b--;
G[a].push_back(b);
G[b].push_back(a);
input.emplace_back(a, b);
}
vector<vector<int>> colors(n, vector<int>(n));
queue<P> que;
que.emplace(0, 0);
int all_color = 1;
while (!que.empty()) {
P v = que.front(); // キューから先頭頂点を取り出す
que.pop();
// v から辿れる頂点をすべて調べる
int used_color = colors[v.first][v.second];
int color = 1;
for (int nv : G[v.first]) {
if (nv == v.second) continue;
if(used_color == color) color++;
colors[v.first][nv] = color;
colors[nv][v.first] = color;
que.emplace(nv, v.first);
chmax(all_color, color);
color++;
}
}
cout << all_color << endl;
rep(i, n-1) {
cout << colors[input[i].first][input[i].second] << endl;
}
return 0;
}
解説放送をみた
https://www.youtube.com/watch?v=7IlBVSglZqc
木はDFSでやろうとのこと
DFSだと再帰関数での実装になる, 関数なので引数で色々情報が渡せるので、
使った色番号や、親の頂点番号などを渡すことでシンプルに実装できるし、メモリ効率も良い
再帰関数としては以下のような感じ
/**
* 色の配色を決める再帰関数
* @param v : 確認する頂点番号
* @param color : 親と確認する頂点を結ぶ辺の色
* @param parent : 親の頂点番号
*/
void dfs(int v, int color, int parent) {
// 次の辺を塗るときに使う色の番号
int c = 1;
// 今の頂点から辿れるやつを確認する
rep(i, g[v].size()) {
// u : 次の頂点, id : 最後の出力用に入力で受け取った辺の番号
int u = g[v][i].to, id = g[v][i].id;
// 親の場合は何もしない
if (u == parent) continue;
// 親から来たときに使った色は使えない
if (c == color) c++;
// 解答用に, cinしたときのindexに色を入れておく
ans[id] = c; c++;
dfs(u, ans[id], v);
}
}
提出コード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
struct Edge { int to, id; };
using Graph = vector<vector<Edge>>;
Graph g;
vector<int> ans;
// 確認する頂点番号, 親と確認する頂点を結ぶ辺の色, 親の頂点番号
void dfs(int v, int color, int parent) {
int c = 1;
// 今の頂点から辿れるやつ
rep(i, g[v].size()) {
int u = g[v][i].to, id = g[v][i].id;
// 親の場合は何もしない
if (u == parent) continue;
// 親から来たときに使った色は使えない
if (c == color) c++;
// 解答用に, cinしたときのindexに色を入れておく
ans[id] = c; c++;
dfs(u, ans[id], v);
}
}
int main() {
int n; cin >> n;
g.resize(n);
ans.resize(n-1);
for(int i=0; i<n-1; i++) {
int a, b; cin >> a >> b;
a--; b--;
g[a].push_back((Edge){b,i});
g[b].push_back((Edge){a,i});
}
dfs(0, -1, -1);
// 使う色数の確認, 一番次数が多いとこの次数=使う色
int color_num = 0;
rep(i, n) chmax(color_num, (int)g[i].size());
cout << color_num << endl;
rep(i, n-1) cout << ans[i] << endl;
return 0;
}