Baekjoon 11725번 트리의 부모 찾기

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
vector<int> visited, ans;
vector<vector<int>> adj;

void solve(int c){
    for(int i = 0; i < adj[c].size(); i++){
        int n = adj[c][i];
        if(!visited[n]){
            visited[n] = 1;
            ans[n] = c;
            solve(n);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    visited.resize(n+1, 0);
    ans.resize(n+1);
    adj.resize(n+1);
    int v, u;
    for(int i = 0; i < n-1; i++){
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    visited[1] = 1;
    solve(1);
    for(int i = 2; i <= n; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

트리는 어떤 노드를 기준으로 들어올려도 트리의 형태가 유지된다.

문제에서는 1번 노드를 루트로 할 때 각 노드의 부모 노드를 구하라고 하였으므로, 1번 노드부터 시작하여 모든 노드를 한번씩 확인해주면 된다.

재귀 dfs 를 이용해 풀이하였다.