【競技プログラミング】AtCoder Beginner Contest 146_D問題

問題

要約

1. 木Gは、N個の頂点と、N-1本の辺で構成される。
2. 頂点には1からNまでの番号が付いている。
3. i番目の辺は、頂点a_iと頂点b_iを結んでいる。

辺の色分けに関する条件：

1. 各頂点に接続する辺の色はすべて異なる必要がある。
2. 使用する色の数を最小にする必要がある。

上記の条件を満たす塗り分け方のうち、使用する色の数が最小となるものを1つ構築すること。

変数情報：

• N: 木の頂点数
• G: 与えられる木
• a_i, b_i: i番目の辺が結ぶ2つの頂点の番号

既存投稿一覧ページへのリンク

一覧ページ

独り言

AtCoderでよく見る「彩色問題」なので、流石に慣れました。

アプローチ

木の辺彩色問題を解くために、深さ優先探索（DFS）を用いて木を走査し、各辺に色を割り当てる。
使用する色の数は、木の最大次数（任意の頂点に接続する辺の最大数）に等しくなる。

解法手順

1. 入力から木の構造を隣接リストとして構築する。
2. 木の最大次数を計算し、これを使用する色の数とする。
3. DFSを用いて木を走査し、各辺に色を割り当てる。
4. 親頂点から子頂点への探索時に、使用可能な最小の色を割り当てる。
5. 親頂点に割り当てた色は子頂点では使用しない。
6. 全ての辺に色を割り当てた後、結果を出力する。

ACコード

ac.py

import sys

def io_func():
    # 再帰の深さ制限を設定
    sys.setrecursionlimit(10**9)
    
    # 頂点数Nを入力から読み取る
    n = int(input())
    
    # N個の空リストを持つ隣接リストgを作成
    g = [[] for _ in range(n)]
    
    # N-1本の辺の情報を入力から読み取り、隣接リストgに追加
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1  # 0-indexedに調整
        b -= 1
        g[a].append((b, i))
        g[b].append((a, i))
    
    return n, g

def solve(n, g):
    # 最大次数sizeを計算し、出力
    size = max(len(x) for x in g)
    print(size)
    
    # 辺の色を格納するリストansを初期化
    ans = [0] * (n-1)
    
    # DFSを行う関数fを定義
    def f(cur, par, col):
        x = 0  # 色のカウンター
        
        for to, i in g[cur]:
            if to != par:
                x += 1
                if x == col:  # 親との辺の色は避ける
                    x += 1
                ans[i] = x
                
                f(to, cur, x)
    
    # 根を0として、DFSを開始
    f(0, -1, -1)
    
    # 各辺の色をansから取り出し、出力
    print(*ans, sep='\n')

if __name__=="__main__":
    # メイン処理
    n, g = io_func()
    solve(n, g)

###
# - n: 頂点の数
# - g: 隣接リスト（各頂点に接続する辺と、その辺のインデックスを格納）
# - size: 最大次数（使用する色の数）
# - ans: 各辺に割り当てられた色を格納するリスト
# - cur: 現在の頂点
# - par: 親頂点
# - col: 親との辺の色
# - x: 現在割り当てている色
# - to: 子頂点
# - i: 辺のインデックス

# 1. io_func関数:
#    - 入力処理を行う
#    - 再帰の深さ制限を設定
#    - 頂点数と隣接リストを返す

# 2. solve関数:
#    - 最大次数を計算し出力
#    - DFSを行うf関数を定義
#    - f関数を使って木を走査し、辺に色を割り当てる
#    - 結果を出力

# 3. f関数（DFS）:
#    - 現在の頂点から子頂点へ探索
#    - 使用可能な最小の色を割り当てる
#    - 親との辺の色は避ける

# 4. メイン処理:
#    - io_func関数で入力を処理
#    - solve関数で問題を解く

思考過程

1. 木の構造を理解し、隣接リストで表現する。
2. 最大次数が必要な色の数と等しいことを認識する。
3. DFSを使って木を効率的に走査する方法を考える。
4. 各辺に色を割り当てる際、親との辺の色を避ける戦略を立てる。

計算量の概算

O(N)、ここでNは頂点の数。DFSで各頂点を1回ずつ訪れるため。
O(N)、隣接リストと結果を格納するリストのサイズ。

その他周辺知識

再帰の深さ制限の設定

sys.setrecursionlimit(10**9)

隣接リストの初期化

g = [[] for _ in range(n)]

木構造を表現

g = [[] for _ in range(n)]
for i in range(n-1):
   a, b = map(int, input().split())
   a -= 1
   b -= 1
   g[a].append((b, i))
   g[b].append((a, i))

このループは、n-1回繰り返される。
各反復で

• 2つの整数aとbを入力から読み取る。
• aとbから1を引いて0-indexedに調整する。
• g[a]に(b, i)のタプルを追加し、g[b]に(a, i)のタプルを追加する。
  ここでiは辺のインデックスを表す。

最大値

size = max(len(x) for x in g)

隣接リストgの各要素（各頂点の隣接リスト）の長さの最大値を計算する。
このsizeが最大次数、つまり必要な色の数となる。

深さ優先探索（DFS）

def f(cur, par, col):
   x = 0
   for to, i in g[cur]:
       if to != par:
           x += 1
           if x == col:
               x += 1
           ans[i] = x
           f(to, cur, x)

この関数fは深さ優先探索（DFS）を実装している。
curは現在の頂点、parは親頂点、colは親との辺の色を表す。

• xは現在割り当てている色を表す。
• 隣接する各頂点toに対して：
  • toが親でない場合、新しい色xを割り当てる。
  • もしxが親との辺の色colと同じなら、xを1増やす。
  • 辺の色をans[i]に格納する。
  • 再帰的にf(to, cur, x)を呼び出す。