/* 
그래프를 인접 리스트로 저장한다
나머지 노드는 비어 있음

visited 배열을 만든다 (처음에는 모두 false)

스택 역할을 할 벡터 st를 만든다
st에 시작 노드 1을 넣는다

while (st가 비어있지 않을 때까지 반복):
    
    현재노드 = st의 마지막 값 꺼내기 (top)
    st에서 마지막 값 제거하기 (pop)

    만약 현재노드를 이미 방문했다면:
        continue (다음 반복으로 넘어가기)

    현재노드를 방문 표시한다
    현재노드를 출력한다

    현재노드와 연결된 모든 이웃 노드를 뒤에서부터 반복:
        next = 이웃 노드
        
        만약 next를 아직 방문하지 않았다면:
            st에 next를 넣는다 (push)

반복이 끝나면 DFS 탐색 종료








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

int main() {
    vector<int> graph[10];

    // 파이썬 graph 리스트 그대로 변환
    graph[1] = {2, 3, 4};
    graph[2] = {5};
    graph[3] = {6, 7};
    graph[4] = {8};
    graph[5] = {};
    graph[6] = {9};
    graph[7] = {};
    graph[8] = {};
    graph[9] = {};

    bool visited[10] = {false};

    // vector를 스택처럼 사용
    vector<int> st;
    st.push_back(1);   // 시작 노드

    while (!st.empty()) {
        int node = st.back();
        st.pop_back();

        if (visited[node]) continue;
        visited[node] = true;

        cout << node << " ";

        // DFS 순서 맞추려고 역순 push
        for (int i = graph[node].size() - 1; i >= 0; i--) {
            int next = graph[node][i];
            if (!visited[next]) {
                st.push_back(next);
            }
        }
    }
}
*/