백준 11725번 : 트리의 부모 찾기

• Solved.ac 기준 : 실버 2
• 사용언어 C++

문제 풀이 및 해석

• DFS나 BFS를 이용해 트리구조를 파악하여 부모를 찾는 문제

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

void findParent(int n, vector<vector<int>>& tree, vector<int>& parents) {
    stack<int> stk;
    stk.push(1);
    parents[1] = 0;

    while (!stk.empty()) {
        int current = stk.top();
        stk.pop();

        for (int i : tree[current]) {
            if (parents[i] == 0) {
                parents[i] = current;
                stk.push(i);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<vector<int>> tree(n+1);
    vector<int> parents(n + 1, 0);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    findParent(n, tree, parents);

    for (int i = 2; i <= n; i++) {
        cout << parents[i] << "\n";
    }

    return 0;
}