Pythonの標準1260問題を分析する

🐒 DFSとBFS

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

私の草

import sys
from collections import deque



n, m, v = map(int, input().split())


graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n+1):
    graph[i].sort()

def dfs(x):
    visited[x] = True
    print(x , end=' ')
    for i in graph[x]:
        if not visited[i]:
            dfs(i)

def bfs(x):
    visited[x] = True
    queue = deque([x])
    while queue:
        x = queue.popleft()
        print(x, end=' ')
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

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

参考資料

🧠 問題を理解する

これはDFSとBFSアルゴリズムの使い方を把握できる問題である.
今はまだ混同していますが、コードを1行1行書いていくと、だんだん理解してきました.
2つ目の例では

5 5 3
5 4
5 2
1 2
3 4
3 1

このように入力する場合
私の出力は

3 4 5 2 1 
3 4 1 5 2

答えを誤る.
答えは.

3 1 2 5 4
3 1 4 2 5

はい.
私の答えが違うのは

for i in range(1, n+1):
	graph[i].sort()

上のコードは各ノードを上に移動する順序で並べていないためです.
順序のない双方向ノードといって、複数の答えがあるのではないでしょうか.
ただし、複数のアクセス可能な頂点がある場合は、まず頂点番号の小さい頂点にアクセスします.
この言葉は見るのが遅くてやっと納得した.😇
世界には賢い人がたくさんいます.