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

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

---

 이해하기

루트가 없는 트리가 주어졌는 데, 트리의 루트를 1이라고 정한다. (??????)

일단 이해한 바로는 각 노드의 부모를 구해야하니 루트가 1로 주어졌으니까 1부터 dfs를 진행시켜서 노드들의 부모를 찾으면 된다.
주어진 간선들이 순서가 없으므로 무방향 그래프로 간주하고 풀어야한다.

이 특징들만 적용해서 일반 dfs 문제처럼 풀었더니 쉽게 풀 수 있었다.

---

최종 코드

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

int n;
int visited[100001] ={0, };
vector<int> v[100001];
//부모 노드를 저장할 배열
int parent[100001];

void dfs(int n){
    visited[n] = 1;
    
    for(int i=0; i<v[n].size(); i++){
        int x = v[n][i];
        if(visited[x]==0) {
            dfs(x);
            parent[x] = n;
        }
    }
}

int main()
{
    cin >> n;
    
    int a, b;
    for(int i=1; i<n; i++){
        cin >> a >> b;
        
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    //루트노드인 1부터 dfs를 진행하면서 parent[] 를 채워넣음
    dfs(1);
    
    // 노드 2부터 부모 노드 출력
    for(int i=2; i<=n; i++){
        cout << parent[i] << "\n";
    }
    
    return 0;
}