[python]バックアップ1260号:DFSとBFS

7382 ワード
白駿 コーディングテスト練習 DFS/BFS パイ テキストリンク

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

注意事項


接続されたノードにアクセスする場合は、まず小さなノードにアクセスします.
点数の11%が常に間違っている場合は、ランキングを確認しましょう.(3番エラーㅠ)

反例

6 8 1
1 6 
6 2 
2 4 
4 3 
3 5 
5 1 
5 6 
2 3
----
1 5 3 2 4 6 
1 5 6 3 2 4
例文:https://www.acmicpc.net/board/view/24356

コード#コード#

import sys
from collections import deque
input = sys.stdin.readline
n, m, v = map(int, input().split())

maps = [[] for _ in range(n+1)]
info  = [list(map(int,input().split())) for _ in range(m)]
for a,b in info:
    maps[a].append(b)
    maps[b].append(a)

visited = [False] * (n+1)
dfs = []

def DFS_Recursive(maps, now):
    visited[now] = True
    dfs.append(now)
    for w in sorted(maps[now]):
        if not visited[w]:
            DFS_Recursive(maps, w)
DFS_Recursive(maps, v)
print(*dfs)

bfs = [v]
q = deque()
q.append(v)

while q:
    now = q.popleft()
    visited[now]=True
    for w in sorted(maps[now]):
        if w not in bfs:
            q.append(w)
            bfs.append(w)
print(*bfs)
tcping、使いやすいTCPポート検出ツール
HTMLの基本概念を整理する