[BOJ] 11725. 트리의 부모 찾기

11725. 트리의 부모 찾기

1. 문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

3. 출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

4. 풀이

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100001
#define endl '\n'

int N;
bool visited[MAX];
int ans[MAX];
vector<int> tree[MAX];

void bfs()
{
    queue<int> q;
    q.push(1);
    visited[1] = true;
    
    while (!q.empty())
    {
        int parent = q.front();
        q.pop();
        
        for (int i = 0; i < tree[parent].size(); ++i)
        {
            int next = tree[parent][i];
            
            if (!visited[next])
            {
                ans[next] = parent;
                visited[next] = true;
                q.push(next);
            }
        }
    }
}


int main()
{
    cin >> N;
    
    int a, b;
    for (int i = 1; i < N; ++i)
    {
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    
    bfs();
    
    for (int i = 2; i <= N; ++i)
        cout << ans[i] << endl;
}