atcoder146dがわからず困ってます。

Question

atcoderで下記問題に対して
問題

下のコードで回答されている方がいて、
この18行目のdef文
dfs(to, x, color)
ここの処理が理解できず困っています。
ご教示よろしくお願いいたします。

import sys 
sys.setrecursionlimit(1000000)
 
n = int(input())
edge = [[] for i in range(n)]
a = [0] * n
b = [0] * n
 
color_dict = {}
k = 0
def dfs(x, last = -1, ban_color = -1):
    global k
    color = 1
    for to in edge[x]:
        if to == last:continue
        if color == ban_color:color += 1
        color_dict[(x, to)] = color
        dfs(to, x, color)
        color += 1
    k = max(k, color-1)


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

dfs(0)
print(k)
 

for i in range(n-1):
    if (a[i], b[i]) in color_dict:
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])

Comments

[CHERRY]

自分自身を呼び出している「再帰処理」がわからないということでしょうか？

[syuheisyosinsya]

はい(汗)
ここでの第１引数toがdef分のxを呼ぶという認識で合ってますでしょうか？

Answer 1

def dfs(x, last = -1, ban_color = -1):

• 今x番目の頂点に居る
• 直前にはlast番目の頂点に居た(-1の時、直前が無い)
• x番目の頂点はban_colorの色で塗ることが出来ない

なので、大体以下のようになると思います

def dfs(x, last = -1, ban_color = -1):
    # 略
    # x に隣接する頂点 to それぞれについて
    for to in edge[x]:
        # 略
        # to へ移動する(直前は今の頂点=x)
        dfs(to, x, color)

「木構造」「深さ優先探索」で似たような実装例が出てくるかもしれません

Comments

[syuheisyosinsya]

とてもわかりやすかったので、ベストアンサーにさせていただきました！
ありがとうございます！！