[Graph Search]Boj 1260:DFSとBFS
1608 ワード
[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)
コード結果
Reference
この問題について([Graph Search]Boj 1260:DFSとBFS), 我々は、より多くの情報をここで見つけました https://velog.io/@kakasi18/Graph-Search-Boj1260-DFS와-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol