[白俊]1260DFSとBFS

質問する

反例

<スコアで87%のランタイムエラー>

1000 1 1
99 1000

反例で知るべき部分

幹線が存在しないノードが存在する->条件を追加する必要があります.

import sys
from collections import deque

# 입력으로 들어온 간선 정보 저장
def makeGraph(points):
    graph = dict()
    for p in points:
    # 간선은 양방향이기 때문에 각각의 노드에 연결된 노드에 대한 정보를 추가해주어야 한다.
    # 모든 노드가 간선을 가지는 것이 아니다.
        if not p[0] in graph.keys():
            graph[p[0]] = []
        if not p[1] in graph.keys():
            graph[p[1]] = []
        graph[p[0]].append(p[1])
        graph[p[1]].append(p[0])
    for g in graph:
        graph[g].sort()
    return graph

def dfs(graph, visited, v):
    visited[v] = True
    print(v, end=' ')
    if v in graph: # 반례를 통해 알아낸 조건 추가
        for i in graph[v]:
            if not visited[i]:
                dfs(graph, visited, i)

def bfs(graph, visited, v):
    queue = deque([v])
    visited[v] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        if v in graph: # 반례를 통해 알아낸 조건 추가
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

def start():
    n, m, v = map(int, sys.stdin.readline().split())

    points = [list(map(int, sys.stdin.readline().split())) for i in range(m)]

    visited_dfs = [0] * (n+1)
    visited_bfs = [0] * (n+1)
    graph = makeGraph(points)
    dfs(graph, visited_dfs, v)
    print()
    bfs(graph, visited_bfs, v)

start()

忘れるたびに

bfs実装にはキューが必要であり,PythonではdequeとQueue実装を用いることができる.
deque

データの双方向追加と削除を可能にする両端キュー

deckと読む

thread-safe、appends、popsのメモリ効率を確保

deque初期化時、deque([5])

from collections import deque

queue = deque([4]) # queue -> 4
queue.append(5) # queue -> 4 5
queue.append(6) # queue -> 4 5 6
queue.popleft() # 4, queue -> 5 6
queue.popleft() # 5, queue -> 6

queue.clear() # queue -> 

Queue

from queue import Queue

queue = Queue()

queue.put(4) # queue -> 4
queue.put(5) # queue -> 4 5
queue.put(6) # queue -> 4 5 6

queue.get() # 4, queue -> 5 6
queue.get() # 5, queue -> 6
queue.get() # 6, queue ->