[1260]DFS와 BFS 프로그램

# N:노드 개수, M:에지 개수, Start:시작점
# A:그래프 데이터 저장 인접 리스트
from collections import deque


N, M, Start = map(int, input().split())
A = [[] for _ in range(N+1)]

# A 인접 리스트에 그래프 데이터 저장
for _ in range(M):
    s, e = map(int, input().split())
    A[s].append(e)  # 양방향 에지이므로 양쪽에 에지를 더하기
    A[e].append(s)

# 방문할 수 있는 노드가 여러 개일 경우에 번호가 작은 것부터 먼저 방문하기 위해 정렬
for i in range(N+1):
    A[i].sort

# DFS 구현하기
def DFS(v):
    print(v, end=' ')
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            DFS(i)

visited = [False] * (N + 1)
DFS(Start)

# BFS 구현하기
# 큐 자료구조에 시작 노드 삽입
# visited 리스트에 현재 노드 방문 기록
def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = True

    # 큐가 비어 있을 때까지:
    # 큐에서 노드 데이터를 가져오기
    # 가져온 노드 출력
    # 현재 노드의 연결 노드 중 미 방문 노드를 큐에 삽입(append 연산)하고 방문 리스트에 기록
    while queue:
        now_Node = queue.popleft()
        print(now_Node, end=' ')
        for i in A[now_Node]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

print()
visited = [False] * (N + 1) # 리스트 초기화
BFS(Start)