徒然weed

アウトプットの場

ゆる〜くpythonの練習「深さ優先探索(スタック)編」

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

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

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

本日の問題はこちら。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
深さ優先探索です。
個人的なポイントはグローバル宣言をしないとtime変数が変わらないところです。
隣接行列は作らずにqueue(deque)を用いて一度通った道をそのつどpop()してます。
結局やっていることはスタックの一番上に乗ってる頂点からまだいける頂点があればその頂点をスタックに追加して、ない場合はpop()しようね、ってだけです。

from collections import deque

n = int(input())
V = []
info = deque([])
# Vはパスの情報を格納している
for i in range(n):
    info = deque(list(map(int,input().split()))[2:])
    V.append(info)
#visit_infoを用意し頂点の状態を初期化
visit_info = ["white" for _ in range(n)]

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

time = 0

def dfs_visit(r):
    stack.append(r)
    visit_info[r-1] = "gray"
    global time #グローバル宣言!
    df[r-1][0] = time+1
    time = time + 1

    while len(stack)!=0:
        u = stack[-1]
        if len(V[u-1])!= 0:
            b = V[u-1].popleft()
            if visit_info[b-1] == "white":
                visit_info[b-1] = "gray"
                df[b-1][0] = time + 1
                time+=1
                stack.append(b)
        else:
            stack.pop()
            visit_info[u-1] = "black"
            df[u-1][1] = time + 1
            time = 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

本日のおまけ
Find your "tennisball",be in a good "circle",and start now cause you only have about "30000" days in your life.
とのことです。さすがドロップボックス創設者、いいこと言う〜。