DFS(stack)

문제 정의

무방향 그래프가 주어졌을 때, 정점 0부터 시작하여 그래프를 깊이우선탐색(DFS)으로 순회하는 알고리즘을 작성하세요.

깊이우선탐색에서 여러 선택지가 존재하게 된다면 항상 가장 번호가 낮은 정점을 우선적으로 선택해서 탐색합니다. 예를 들면 정점 0을 방문한 뒤에 정점 2 혹은 정점 5를 방문할 수 있다면, 낮은 번호인 2번 정점을 먼저 탐색합니다.
참고사항

재귀함수를 이용해서 구현하는 경우, 다음의 코드를 위에 작성해두셔야 정상적으로 작동합니다.
import sys
sys.setrecursionlimit(1000000)

입력 형식

입력의 첫 줄에 테스트 케이스의 숫자 t가 주어진다.
각 테스트 케이스마다 입력은 아래와 같다.

첫 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (N≤1,000,M≤100,000)
그 다음 M개의 줄에 걸쳐서 그래프의 간선 (u,v)가 공백을 사이에 두고 입력된다. u와 v는 항상 0부터 N−1

사이의 정수이고, 두 정점 간 간선은 유일하다.
그래프는 연결되어 있다.

출력 형식

각 테스트 케이스에 대해 정점 0에서 시작하여 깊이우선탐색으로 그래프를 탐색했을 때 정점이 방문되는 순서를 한 줄에 공백을 두고 출력한다.

입력 예시

3
4 4
0 1
0 3
1 2
1 3
5 7
0 1
0 2
0 4
1 3
1 4
2 4
3 4
6 5
0 5
5 4
1 4
1 3
2 3

출력 예시

0 1 2 3
0 1 3 4 2
0 5 4 1 3 2

t = int(input())
for _ in range(t):

    N, M = map(int, input().split())

    Li = [[] for _ in range(N)]

    for i in range(M):
        u, v = map(int, input().split())
        Li[u].append(v)
        Li[v].append(u)

    sorted(Li)

    for i in range(N):
        Li[i].sort()
        print(*Li[i])