// 입력:
//     그래프 graph (인접 리스트)
//     정점의 개수 N
//     시작 정점 start

// 준비:
//     visited 배열을 크기 N으로 만들고 모두 false로 초기화
//     빈 스택 stack을 만든다

// 1. 스택에 시작 정점 start를 넣는다

// 2. 스택이 비어있지 않은 동안 반복한다
//     2-1. 스택의 맨 위 정점을 꺼내서 cur에 저장한다

//     2-2. 만약 cur가 이미 방문된 정점이면
//          다음 반복으로 넘어간다

//     2-3. cur를 방문 처리한다
//          (visited[cur] = true)
//          cur를 출력한다 (또는 방문 기록)

//     2-4. cur와 인접한 모든 정점을 확인한다
//          (뒤에서부터 확인하면 재귀 DFS와 순서가 비슷해진다)

//          각 인접 정점 next에 대해
//              만약 next가 아직 방문되지 않았다면
//                  스택에 next를 넣는다

// 3. 스택이 빌 때까지 반복하면 DFS 종료


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N = 8;        // 노드 개수
    int start = 0;    // 시작 노드

    vector<vector<int>> graph(N);

    graph[0] = {1, 2, 3};
    graph[1] = {0, 2};
    graph[2] = {0, 1, 3, 4};
    graph[3] = {0, 2, 5, 6};
    graph[4] = {2};
    graph[5] = {3, 6, 7};
    graph[6] = {3, 5};
    graph[7] = {5};

    vector<bool> visited(N, false);
    vector<int> stack;

    // 시작 노드 push
    stack.push_back(start);

    while (!stack.empty()) {
        int cur = stack.back();
        stack.pop_back();

        if (visited[cur]) continue;

        visited[cur] = true;
        cout << cur << " ";

        // 인접 노드를 역순으로 push
        for (int i = graph[cur].size() - 1; i >= 0; i--) {
            int next = graph[cur][i];
            if (!visited[next]) {
                stack.push_back(next);
            }
        }
    }

    return 0;
}