徒然weed

アウトプットの場

ゆる〜くpythonの練習「深さ優先探索(再帰)編」

f:id:shintaro-football7:20191022195746p:plain

前回に引き続き深さ優先探索について。問題も同じです。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
再帰は難しいですよね〜。
参考サイト:
qiita.com

個人的には↓の本の8.4「木の巡回」(
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C
)が再帰を理解するのに結構いいと思います

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

from collections import deque

n = int(input())
V = []
info = []
for i in range(n):
    info = deque(list(map(int,input().split()))[2:])
    V.append(info)
visit_info = ["white" for _ in range(n)]

df = [[0]*2 for _ in range(n)]

time = 0

def dfs_visit(u):
    global time
    df[u-1][0] = time+1
    time+=1
    visit_info[u-1] = "gray"
    while(len(V[u-1])!=0):
        a = V[u-1].popleft()
        if visit_info[a-1]=="white":
            dfs_visit(a)
    visit_info[u-1] = "black"
    df[u-1][1] = time+1
    time +=1


for i in range(1,n+1):
    if(visit_info[i-1] == "white"):
        dfs_visit(i)
i = 1
for v in df:
    print(i,*v)
    i+=1

この企画に加えて、あと何個か企画を検討中です。暇な人はぜひ読んでね〜(『本日のおまけ』だけでも)。



本日のおまけ