問題
考えたこと
- 絵を書いてみる
- 最大の色の数は最も枝の多い頂点の数になる
- 色をどうやって分けるかが大きな課題
- 最初は各頂点に k 種類の set をもたせて 1個ずつ pop させていくか？と思ったけど,
TLE しそうだし, 実際にしたので駄目だった.
- 考え直したら, 幅優先探索で頂点移動の際に使った色を渡していけば, 次の頂点ではその色だけ使わないようにできるじゃん, と気づく
- 手計算でも問題なく動いたため, 実装に取り掛かってみる
実装
from collections import defaultdict
from collections import deque
n = int(input())
graph = defaultdict(set)
line = []
k = 0
for _ in range(n-1):
a, b = [int(x) for x in input().split()]
line.append((a, b))
graph[a].add(b)
graph[b].add(a)
k = max(k, len(graph[a]), len(graph[b]))
print(k)
queue = deque()
queue.appendleft((1, -1))
end = set()
end.add(1)
ans = dict()
while queue:
now, use_color = queue.pop()
color = 1
for next_node in graph[now]:
x = min(now, next_node)
y = max(now, next_node)
if not next_node in end:
if color == use_color:
color += 1
queue.append((next_node, color))
end.add(next_node)
ans[(x, y)] = color
color += 1
for x, y in line:
print(ans[(x, y)])
結果
- 無事に
AC できた
- グラフ問題が出てきたら 幅優先探索, 深さ優先探索, あたりはぱっと思いついて行けるか行けないか手計算で判断していきたいところ
