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

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

11725번: 트리의 부모 찾기

 본 문제는 트리로 연결된 두 정점을 입력으로 들어오면 2번 노드부터 부모 노드를 출력하는 문제다. ( 단, 1을 root로 한다. ) 따라서, 모든 연결 정보를 인접 리스트에 저장하고 root부터 BFS를 이용해 탐색을 하면서 각 노드의 부모 노드를 저장한다. 2번 노드 부터 n까지 반복하면서 부모노드를 출력한다.

#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> v[100001];
int d[100001];
bool chk[100001];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    queue<int> q;
    chk[1] = true;
    q.push(1);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < v[node].size(); i++) {
            int next = v[node][i];
            if(!chk[next]) {
                chk[next] = true;
                q.push(next);
                d[next] = node;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        printf("%d\n", d[i]);
    }
}