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

문제

백준 11725 트리의 부모 찾기 C++

11725번: 트리의 부모 찾기

풀이

1이 루트기 때문에, 1에서 DFS나 BFS를 실행하면 된다.

해당 노드에 처음 방문했을 때, 그 전 노드가 부모가 된다.

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
int N;
int parent[100001];
int visited[100001];
vector<int> graph[100001];
 
void BFS()
{
    queue<int> q;
    q.push(1);
    visited[1] = true;
 
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
 
        for (int next : graph[cur])
        {
            if (!visited[next])
            {
                visited[next] = true;
                parent[next] = cur;
                q.push(next);
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N;
 
    int a;
    int b;
 
    for (int i = 0; i < N - 1; i++)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    BFS();
 
    for (int i = 2; i <= N; i++)
    {
        cout << parent[i] << '\n';
    }
 
    return 0;
}