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

트리의 부모 찾기 실버2

문제

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

입력

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

출력

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

풀이

• bfs문제로 벡터로 인접트리구현 후 bfs돌면서 부모 표시. 부모 출력.
• 주의할 점은 입출력이 많기에 stdio사용 & ios_base::sync_with_studio(0); cin.tie(0)설정 필요.

코드

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

vector<int> tree[100001];
int visited[100001];
int parent[100001];

void init()
{
    for(int i = 0; i < 100001; i++)
    {
        visited[i] = 0;
        parent[i] = 0;
    }
    // cout << "init!" << endl;
}

void bfs()
{
    queue<int> q;
    int size = tree[1].size();
    visited[1] = 1;
    for(int i = 0; i < size; i++)
    {
        int child = tree[1][i];
        visited[child] = 1;
        parent[child] = 1;
        q.push(child);
    }

    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        int n_size = tree[node].size();
        for(int i = 0; i < n_size; i++)
        {
            int child = tree[node][i];
            if(visited[child] == 0){
                visited[child] = 1;
                parent[child] = node;
                q.push(child);
            }
        }
    }

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;

    for(int i = 0; i < n - 1; i++)
    {
        int f, s;
        cin >> f >> s;
        tree[f].push_back(s);
        tree[s].push_back(f);
    }
    init();
    bfs();

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


}

• ps
• bfs