문제 번호 : 깊이우선탐색(DFS)

문제 번호 : 깊이우선탐색(DFS)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 77  해결 문제 수: 24
[제출][채점상황][게시판][:]

문제 설명

깊이우선탐색(DFS)는 그래프의 임의의 한 정점에서 출발하여, 연결된 정점들 중 하나에 대해서 깊이 순으로 먼저 탐색해 나가는 탐색법이다. 예를 들어 다음과 같은 그래프를 보자.

이를 정점 1을 시작으로 깊이우선 탐색을 했을 경우 여러가지가 가능하지만 가능한 경우의 한 가지는

1 2 3 5 6 4 이다.

따라서 하나의 결과를 위해 다음과 같은 제약조건을 적용한다.

1. 정점 1부터 방문한다.

2. 한 정점에서 갈 수 있는 곳이 여러개 있을 경우 먼저 입력된 정점부터 방문한다.

3. 어떤 정점과 연결되지 않은 경우는 번호가 빠른 순으로 방문한다.

주어진 그래프는 양방향 무가중치 그래프이다.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.

둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.

이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

DFS결과를 출력하라.

입력예시

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

출력예시

1 2 3 5 6 4 7

도움말

[제출][채점상황]