ABC146D
当内容は、他サイトを参考に自分用に編集したものです。
はじめに
- 次数 (つながる辺の本数) が最大の頂点がボトルネックになる
- 次数の最大値を d とすると、d 色で塗り分けられそう
もし「具体的な塗り分け方を求めよ」と言われなければ、最大次数を出力してしまって良さそう。でも今回は、具体的な塗り方を求めることも要求されている。それは証明も込みで要求されているのに等しい。
木なので
今回は一般のグラフではないので割と考えやすい。ちなみに今回の問題、一般のグラフの場合は最大次数色では塗りきれないケースが存在する (最大次数色 + 1 で塗ることは可能)！！！！
それはさておき、木を扱うときに定番となる考え方は「根を一つテキトーに決めてしまう」というのがある。これをすると木の頂点にある種の順序付けができるのだ。下図の左側のグラフで青い矢印で示したように、頂点を 1 つ選んで根にすると、下のグラフのような根付き木になる。
そうすると、根頂点から順番に、その隣接辺の色を決めていけば良さそうに思えてくる (DFS でも BFS でもよい)。ここで注目したいのは
新たな頂点について、その隣接辺たちに色を塗ろうとするとき
その隣接辺たちのうち、すでに色が塗られてしまっているのは一本だけ
ということだ。その一本というのは「親頂点」に他ならない。よって、その一色を避けるように色付けすればよいだけだ。
DFS でも BFS でも
木の探索の仕方は、DFS でも BFS でもどちらでもいい。重要なことは、根付きにおいて、どの 2 つの頂点 u, v についても、
- u が v の先祖 (v が u の子孫) であるとき
- u が先に処理されていて、その後 v を処理する
という風にすることだ。計算量はいずれにしても O(N) となる。
サンプルコードは、BFSによるもの。
参考
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
サンプルコード
from collections import deque
# 辺数
n=int(input())
# 辺
G=[[] for i in range(n+1)]
G_order=[]
for i in range(n-1):
a,b=map(int,input().split())
# a,(<)bを紐付け
G[a].append(b)
# 頂点bをリスト
# 頂点bと行数と辺は１対１対応（∵木に閉路はない）
G_order.append(b)
# BFSのデータフレーム
q=deque([1]) # 頂点1を始点とした[訪問キュー]
color=[0]*(n+1) # 頂点の上にある辺の色[フラグ]
# BFS 開始 (キューが空になるまで探索を行う)
while q:
cur=q.popleft() # キューから先頭頂点(現在地)v取得
c=1 # 頂点を移動したら色を初期化
# 現在点から伸びる辺に色を付ける
for nx in G[cur]:
# 現在点の上辺と同じ色なら変更
if c==color[cur]:
c+=1
color[nx]=c
c+=1
q.append(nx) # 訪問先（頂点）を追加
print(max(color)) # 使用色数
for i in G_order:
print(color[i])