［Graph Search］Boj 1260:DFSとBFS

［Graph Search］Boj 1260：DFSとBFS

Link: https://www.acmicpc.net/problem/1260

質問する

DFSを使用してグラフィックをナビゲートし、BFSを使用してグラフィックをナビゲートした結果を出力するプログラムを作成します.ただし、複数のアクセス可能な頂点がある場合は、最初にアクセスできる頂点番号が小さく、アクセスできるポイントがない場合は終了します.頂点番号は1番からN番までです.

入力

1行目は頂点の個数N(1≦N≦1000)、幹線の個数M(1≦M≦10000)、探索を開始する頂点の番号Vを与える.次のM行は、幹線接続の2つの頂点の番号を示します.2つの頂点の間に複数の幹線があります.入力された幹線は双方向です.

しゅつりょく

1行目はDFSを実行した結果を出力し、2行目はBFSを実行した結果を出力する.Vから順にアクセスポイントを出力すればよい.

I/O例

コード|Python

import sys
from collections import deque
si = sys.stdin.readline

N,M,V = list(map(int,si().split()))
g = [[] for _ in range(N+1)]

for _ in range(M):
    a,b = list(map(int,si().split()))
    g[a].append(b)
    g[b].append(a)

for i in range(1,N+1):
    g[i].sort()

dfs_check = [0] * (N+1)
def dfs(start):
    dfs_check[start] = 1
    print(start,end=" ")
    for x in g[start]:
        if dfs_check[x] == 1: continue
        dfs(x)

bfs_check = [0] * (N+1)
def bfs(start):
    queue = deque()
    queue.append(start)
    bfs_check[start] = 1
    while queue:
        x = queue.popleft()
        print(x, end=" ")
        for y in g[x]:
            if bfs_check[y] == 1: continue
            bfs_check[y] = 1
            queue.append(y)

dfs(V)
print()
bfs(V)

コード結果