[BOJ] 11725

트리의 부모 찾기

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

분류

• Silver 2

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

해법

모든 노드의 부모를 찾는 문제입니다.
갈 수 있는 자식을 모두 기록해서 DFS를 돌면서 부모를 기록해주면 됩니다.

정답 코드

/*
BOJ 11725: 트리의 부모 찾기
*/

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> child[100005];
int parent[100005];
int visited[100005];
int a, b;

void dfs(int cur) {
    visited[cur] = 1;

    for (int i : child[cur]) {
        if (visited[i]) continue;
        parent[i] = cur;
        dfs(i);
    }
}


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        child[a].push_back(b);
        child[b].push_back(a);
    }
    dfs(1);
    for (int i = 2; i <= N; i++) {
        cout << parent[i] << "\n";
    }
    return 0;
}