[백준] 24444 알고리즘 수업 - 너비 우선 탐색 1

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

n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 노드 번호
visited = [0] * (n+1) # 방문 체크 여부 배열
graph = [ [] for _ in range(n+1)] # 노드별 인접 정점 정보

ans = [0] * (n+1) # 노드별 방문 순서 저장
ans_idx = 1
# 노드별 인접 정점 정보 저장
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
# 그래프 정보 오름차순 정렬
for list in graph:
    list.sort()
# bfs 탐색
def bfs(graph, r, visited):
    queue = deque()
    queue.append(r) # 시작 노드 삽입 & 방문 처리
    visited[r] = True

    while queue:
        # 큐에서 삭제 & 출력
        global ans_idx
        v = queue.popleft()
        ans[v] = ans_idx # v번 노드 출력 순서 기록
        ans_idx += 1
        # 방문 안한 인접 노드들 모두 삽입 & 처리
        for i in graph[v]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = True

bfs(graph, r, visited)
for val in ans[1:]:
    print(str(val))