ABC146 D - Coloring Edges on Tree (400)

概要

N頂点の木が与えられる。各辺に色を付けて塗り分けることを考える。同じ頂点から出ている辺に同じ色がつかないように塗り分けることとしたとき、必要な色の種類の最小値と塗り分けの方法を1つ出力せよ。

制約

2 ≦ N ≦ 10^5

方針

色の種類の最小値は、各頂点の入次数（=出次数）の最大値となる。
塗り分け方法は木を根付き木として考え、根からBFSを行う。
根から順に頂点pとその頂点の子x1, x2, ... とを結ぶ辺に色を付けてゆく。頂点pから出ている辺は、(pの親 - p), (p - x1), (p - x2), ...である。
pからx1, x2, ...とを結ぶ辺の色付けの際にはすでに(pの親 - p)の色付けが終わっていることに注意する。実際に塗るときは、(pの親 - p)の辺の色cを覚えておき、color = 1からスタート(解答のコードだとcur)してcolor = cとなったときにcをスキップすればよい。

感想

構築の実装がうまくいきませんでした。解説を見て納得しました。

解答

Submission #8973497 - AtCoder Beginner Contest 146

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	vector<int> g[n];
	vector<pii> es;
 
	rep(i, n-1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		if(b < a) swap(a, b);
		g[a].push_back(b);
		g[b].push_back(a);
		es.push_back({a, b});
	}
 
	vector<bool> visited(n, false);
	queue<int> q;
	q.push(0);
	visited[0] = true;
 
	int cur = 1;
	vector<int> cs(n, 0);
 
 
	int K = 0;
	map<pii, int> col;
 
	while(!q.empty()){
		int p = q.front(); q.pop();
		if(K < g[p].size()) K = g[p].size();
 
		int cur = 1;
		for(int x: g[p]){
			if(visited[x]) continue;
			if(cur == cs[p]) cur++;
			cs[x] = col[(pii){p, x}] = col[(pii){x, p}] = cur;
			cur++;
			visited[x] = true;
			q.push(x);
		}
	}
 
	cout << K << endl;
	for(pii e : es) cout << col[e] << endl;
}