[백준 11725번] 트리의 부모 찾기 (C++)

아이디어

처음엔 뭔문제인가 했다.

그냥 노드 1번부터 DFS하면 DFS들어가기 전 노드N은 DFS들어간 노드 N+1의 부모가 되는 논리

 

C++풀이

#include <bits/stdc++.h>

using namespace std;
vector<int> v[100001];
bool visited[100001];
int parent[100001];
int N;

void dfs(int node, int prev)
{
    parent[node] = prev; // 해당 단계로 넘어오면 이전 노드는 부모이므로.

    for(int i = 0 ; i< v[node].size(); i++)
    {
        if(visited[v[node][i]] == false){ //방문하지 않은 노드 방문.
            visited[v[node][i]]=true;
            dfs(v[node][i],node);
            visited[v[node][i]]=false;
        }
    }
    return;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0 ; i< N-1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    } //트리 생성
    visited[1] = true; //1번부터 시작, 방문했다고 표시.
    dfs(1,1);

    for(int i = 2; i<= N; i++)
    {
        cout << parent[i] << " " ;
    }
}