競プロ初中級者100問

ALDS1 11B 深さ優先探索

この記事で使うアルゴリズム

深さ優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja

この問題は深さ優先探索で解くことができます。

方針

深さ優先探索はスタックや再帰で実装することができますが、今回は再帰で実装します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N = int(input())
adj = [[] for i in range(N)]
for n in range(N):
    V = list(map(int, input().split()))
    for v in V[2:]: # u,k,v1,v2,...
        adj[n].append(v-1)
d = [0] * N # 発見時刻
f = [0] * N # 完了時刻

def dfs(v, t):
    t+=1 # 発見したらインクリメント
    d[v] = t
    for next in adj[v]:
        if d[next] == 0: # 未発見なら
            t = dfs(next, t)
    t+=1 # 完了してもインクリメント
    f[v] = t
    return t

t = 0
for n in range(N):
    if d[n]==0: # 未発見なら
        t = dfs(n,t)
    print (n+1,d[n],f[n])

記事情報

  • 投稿日：2020年5月24日
  • 最終更新日：2020年5月24日