트리의 부모 찾기 11725 (백준으로 C++ 공부하기 35일차)

문제

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

11725번: 트리의 부모 찾기

생각

트리의 루트와 노드의 기본에 대해 이해하기 좋은 문제이다.

코드

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

int main() {
    int n; cin >> n;
    vector<int> v[100001];
    bool vst[100001];
    int arr[100001];

    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    queue<int> q;
    q.push(1);
    vst[1] = true;
    while(!q.empty()) {
        int num = q.front();
        q.pop();

        for(int i = 0; i < v[num].size(); i++) {
            int node = v[num][i];
            if(!vst[node]) {
                arr[node] = num;
                q.push(node);
                vst[node] = true;
            }
        }
    }

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