ABC146 D - Coloring Edges on Tree

AtCoder Beginner Contest 146
atcoder.jp

解法

　まず、使用する色の数はすべての頂点の次数のうち最大のものである（次数とは頂点から出る辺の数である）。
　次に、色の塗分けは幅優先探索を使って行う。具体的には任意の頂点を根として、子となる頂点との間の辺に1から順番に色を与えていく。このとき、根以外の頂点については1つの親が存在するため、親とは何番の色の辺でつながっているかを管理しておき、子となる頂点への色分けにはその色を使わないようにする必要がある。

ソースコード（Python3）

from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    AB=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        AB.append(str(a)+" "+str(b))

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    ans=dict()
    #bfs
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                ans[str(min(now,x))+" "+str(max(now,x))]=color
                color+=1
        color-=1
        K=max(K,color)

    #出力
    print(K)
    for key in AB:
        print(ans[key])
        
if __name__=="__main__":
    main()