from collections import deque
import sys
input = sys.stdin.readline
n,m,v=map(int,input().split())#정점,간선,시작노드
g = [[0] * (n + 1) for i in range(n + 1)] #n+1개의 노드를 가진, 0으로 초기화 된 그래프 생성
for i in range(m):
x,y=map(int,input().split())
g[x][y],g[y][x]=1,1
arr_dfs=[0]*(n+1)
arr_bfs=[0]*(n+1)
def dfs(dv):#스택 or 재귀
arr_dfs[dv]=1
print(dv,end=' ')
for i in range(n+1):
if arr_dfs[i]==0 and g[i][dv]:#해당 노드에 접근한적 있는지, 간선이 있는지
dfs(i)
def bfs(bv):#큐, 큐가 빌 때까지 반복
arr_bfs[bv]=1
dq=deque()
dq.append(bv)
while dq:
node=dq.popleft()
print(node,end=' ')
for i in range(n+1):
if arr_bfs[i]==0 and g[i][node]:#해당 노드에 접근한적 있는지, 간선이 있는지
dq.append(i)#노드 삽입
arr_bfs[i]=1#방문했다고 표시
dfs(v)
print()
bfs(v)
DFS와 BFS의 기본 구현을 묻는 문제이다.
DFS는 깊이우선탐색으로 모든 노드를 방문하고, 스택이나 재귀함수로 구현한다.
BFS는 너비우선탐색으로 두 노드 사이 최단 경로를 방문하며 큐로 구현한다.