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

0. 제목

• 백준 11725 트리의 부모 찾기
• BOJ 11725 트리의 부모 찾기
• C++ 11725 트리의 부모 찾기

---

1. 문제

https://www.acmicpc.net/problem/11725

---

2. 풀이

• DFS를 이용하였다.
• 먼저, vector를 이용해 양방향으로 모두 연결시켜주었다.
• DFS를 하면서 나아가려는 방향의 노드가 아직 방문하지 않은 상태라면 그 노드를 탐색하게 되고 그와 동시에 방금 있었던 노드를 새로 간 노드의 부모로 설정해주었다.
• 루트가 1이므로 1부터 DFS를 실시하고 2번 노드의 부모부터 차례로 출력해주면 된다.

---

3. 코드

#include <iostream>
#include <vector>
using namespace std;
 
#define MAX 100001
 
vector<int> v[MAX];
int parent[MAX];
bool visited[MAX];
int N;
 
void findParent(int x){
    visited[x] = true;
    for(int i = 0; i < v[x].size(); i++){
        int next = v[x][i];
        if(visited[next] == false){
            parent[next] = x;
            findParent(next);
        }
    }
}
 
int main(int argc, const char * argv[]) {
    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);
    }
    
    findParent(1);
    
    for(int i = 2; i <= N; i++)
        cout << parent[i] << '\n';
    
    return 0;
}