[Algorithm][dfs, bfs] 백준 1260 : dfs와 bfs

"""
1. 아이디어
- DFS : 재귀
- BFS : Queue
2. 시간복잡도
- graph 초기화 : O(N^2)
- BFS : O(N+M)
- DFS : O(N+M)
3. 자료구조
- BFS graph : bool[N+1][N+1] 사용 (popleft가 구현되어있다. 시간복잡도가 낮다)
- visited : bool[N+1]
- BFS deque
4. 학습
- 4방향 벡터는 2차원 행렬에서 필요. 이 문제는 1차원 리스트 형태.
- queue의 FIFO 특성을 구현한 것: deque
"""
import sys
from collections import deque
input = sys.stdin.readline

N,M,V = map(int, input().split())
graph = [[False]*(N+1) for _ in range(N+1)]
# 간선 체크
for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b]=True
    graph[b][a]=True

visited1 = [False]*(N+1)
visited2 = [False]*(N+1)

def dfs(V):
    visited1[V]=True
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i]==True and not visited1[i]:
            dfs(i)
def bfs(V):
    q = deque([V])
    visited2[V]=True
    while q:
        V = q.popleft()
        print(V, end=' ')
        for i in range(1, N+1):
            if graph[V][i]==True and visited2[i]==False:
                visited2[i]=True
                q.append(i)

dfs(V)
print()
bfs(V)