ABC146 D - Coloring Edges on Tree - greentomatotan’s blog

(1)問題

(2)問題概要

1からNまでの番号がついたN頂点の木Gが与えられる。Gの辺を何色かで塗り分ける。一つの頂点から出る辺は全て違う色にするとき最小で何色で塗り分けられるかを求め、塗り方を一つ構築せよ。

(3)前提知識

・N頂点の木の辺の数はN-1個（一つの頂点に辺と頂点のペアが何個かくっついていると考えるとイメージできる。）

(4)解法

まず、最小で何色で塗り分けられるかを求める。各頂点から出る辺の数のうち最大の数をMとする。適当な頂点を根として親から子の方向に色を塗っていくと考えると根は子に全て違う色の辺を繋ぎ、他の頂点は親から繋がれた頂点と違う色で子に全て違う色の辺を渡す必要がある。M色あれば全ての頂点で条件を満たすように塗れるので必要な色の数の最小値はMであることが分かる。

次に塗り方の構築を考える。作るものは繋がれている頂点と辺の色がペアとなっている隣接リストである。この隣接リストが作れたらこれを参照して問題で求められている出力をすることができる。計算量を減らすために作る隣接リストはpairではなくmapにする。つまりN個のmapからなる配列MCを作り、MC[i]にはkeyがiから繋がれている頂点、valueが辺の色であるmapが入っている。

色は貪欲に塗っていけばいい。つまりMC[i]のまだ塗られていない要素のvalueに0,1,2,...と順に色を振り分けていけばいいがMC[i]のもうすでに塗られている色は塗ってはいけない。ある色がMC[i]のvalueにもう存在するかの判定にsetを使う。すなわちN個のsetの配列SCを持っておき、SC[i]には頂点iから出る辺にもうすでに塗られた色を入れておく。そしてMC[i]に色を追加していくときにはSC[i]を参照すればもう使われている色が分かる。

MCに対するvalueの更新の仕方を整理する。塗る色を持つcolorという整数の変数を用意しておき、各MC[i]についてcolorを0からはじめ、塗ったらcolorを1増やす。塗るときはMC[i][key]のvalueをcolorに変更すると同時にMC[key][value]の値をcolorに変更する。さらにSC[i]とSC[key]にcolorを挿入する。colorで塗れるかはSC[i]にcolorが存在するかで判定し、存在する場合は塗れないので塗らずにcolorを1増やす。

(5)ソースコード

int V;
cin >> V;
int E = V - 1;//辺の数
vector<int>A(E);
vector<int>B(E);
rep(i, E) {
	cin >> A[i] >> B[i];
         //0-index にする
	A[i]--;
	B[i]--;
}
vector<vector<int>>G(V);//隣接リスト
rep(i, E) {
	G[A[i]].push_back(B[i]);
	G[B[i]].push_back(A[i]);
}
int max_color = 0;
rep(i, V) {
	max_color = max(max_color, int(G[i].size()));
}

vector<set<int>>SC(V);
vector<map<int, int>>MC(V);
rep(i, V) {
	rep(j, G[i].size()) {
		MC[i][G[i][j]] = -1;//色を-1(まだ塗られていない)で初期化
	}
}

int color = 0;
map<int, int>::iterator it;
rep(i, V) {
	color = 0;
	for (it = MC[i].begin(); it != MC[i].end(); it++) {
		if (it->second == -1) {
			while (1) {
				if (SC[i].count(color)) {
					color++;
				}
				else {
					it->second = color;
					MC[it->first][i] = color;
					SC[i].insert(color);
					SC[it->first].insert(color);
					break;
				}
			}
		}
	}
}

cout << max_color << endl;
rep(i, E) {
	cout << MC[A[i]][B[i]] + 1 << endl;
}