Python3で解く AtCoder Beginner Contest 146 D - Coloring Edges on Tree

木グラフにおける辺彩色の問題。色分けに必要な最小な色数とその例をだす必要があるので、色分けの仕方をきちんと書き上げる必要がある。 DFSとBFSの違いを理解した状態で取り組んだので形式的だが、どちらもdequeを使ってやってみた。

目次

概要

問題

1. 個の頂点がある木がある。
2. 本目の辺は頂点と頂点を結んでいる。
3. 辺彩色をするので、塗り分けられる最小の値は？
4. その時の１例を列挙できる？

---

解くときに考えた内容

• 辺彩色
• 辺彩色は以下の定理がある。

  König（ケーニグ・ケーニヒ）の定理
  

  二部グラフにおいて、辺彩色数は、最大次数に等しい。

• 木は二部グラフなので、辺彩色数は、最大次数を求める。
• 最大次数を出すのは隣接行列から出せる。
• 実際に順番を指定された彩色する必要があるので、DFSでもBFSでも良いので、親子関係とpopした順番も保持しておく。
• popした順番ごとに彩色していく。

  彩色のやり方

  • 自分の辺色（親から自分に向かっていく色。子に色を与えると考える）を保持するためのリストを作る。 （カラーリストとする）
  • popするたびに自分の辺色を保持する。
  • 色を初期化(1から始める)する。
  • forで隣接行列から自分の子の情報をとる。（親は無視するようにする。）
  • 子に色をつける。保持している自分の辺色と現在の色の数値が同じなら+1する。
  • カラーリスト[子のindex]に色の数値を入れる。
  • その他の子の色は変えなくてはいけないので、数値が同じなら+1する。
  • 最後の出力で気をつけるのは、今保持している辺色は親から自分に向かっていく色としているので、頂点と頂点のリストにおいて、頂点の親が頂点でない場合は→という関係 （親→子）なので頂点の色を出力。そうでない場合はの出力するとする必要がある。

---

コード

DFS

n = int(input())
adj = [[]for i in range(n+1)]
ab = [list(map(int, input().split())) for i in range(n-1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)
# dequeを使ったスタックによるDFS
# 子をindexで、親ノードを要素で
# 今回は彩色のためにどんな順番でpopされたかも保持しておく
order  = []
parent = [0] * (n+1)
visited = [0] * (n+1)
visited[1] = 1
q = deque([1])
while q:
    par = q.popleft()
    order.append(par)
    for chl in adj[par]:
        if visited[chl]:
            continue
        # 行ったことなかったら1へ
        visited[chl] = 1
        parent[chl] = par
        q.append(chl)
# 彩色
# 親と同じにならないように若い番号を割り当てて行く
cl = [None] * (n+1)
for par in order:
    # 親の色
    pc = cl[par]
    # 彩色は1以上k以下
    color = 1
    for chl in adj[par]:
        # 隣接リストの親は無視
        if chl == parent[par]:
            continue
        # 親の色と同じなら色を変える
        if pc == color:
            color += 1
        # カラーリストに子indexにcolorを入れる
        cl[chl] = color
        #　他の子は色を変える必要がある
        color += 1
# 木グラフなので単純に次数最大で考えて問題ない
g = max([len(i) for i in adj]) 
print(g)   
for a, b in ab:
    # 親子関係が逆転しない出力ならこれでいいがそうとも限らない 
    if parent[a] != b:
        print(cl[b])
    else:
        print(cl[a])

BFS

n = int(input())
adj = [[]for i in range(n+1)]
ab = [list(map(int, input().split())) for i in range(n-1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)
# # dequeを使ったキューによるBFS
# 子をindexで、親ノードを要素で
# 今回は彩色のためにどんな順番でpopされたかも保持しておく
order  = []
parent = [None] * (n+1)
q = deque([1])
while q:
    par = q.popleft()
    order.append(par)
    for chl in adj[par]:
        if chl == parent[par]:
            continue
        parent[chl] = par
        q.append(chl)
# 彩色
# 親と同じにならないように若い番号を割り当てて行く
cl = [None] * (n+1)
for par in order:
    # 親の色
    pc = cl[par]
    # 彩色は1以上k以下
    color = 1
    for chl in adj[par]:
        # 隣接リストの親は無視
        if chl == parent[par]:
            continue
        # 親の色と同じなら色を変える
        if pc == color:
            color += 1
        # カラーリストに子indexにcolorを入れる
        cl[chl] = color
        #　他の子は色を変える必要がある
        color += 1
# 木グラフなので単純に次数最大で考えて問題ない
g = max([len(i) for i in adj]) 
print(g)   
for a, b in ab:
    # 親子関係が逆転しない出力ならこれでいいがそうとも限らない 
    if parent[a] != b:
        print(cl[b])
    else:
        print(cl[a])

---