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

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

11725번: 트리의 부모 찾기

 

입력되는 간선정보를 바탕으로 각 노드의 부모를 저장하면 된다.

 

트리는 항상 n개의 노드가 있을 때 간선이 n-1개이므로 우리는 n-1개의 간선만 입력받아도 트리를 만들 수 있다.

 

처음에 일차원배열로 풀었다가 틀렸다. 왜냐하면 간선 정보가 depth가 깊어지는 순서대로 입력된다는 보장이 없기 때문이다.

따라서 그래프 입력받듯이 모든 간선 정보를 vector에 저장한 후 한번에 트리를 만들어야 한다.

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAX 100003
 
vector<int> v[MAX];
int par[100001];
bool visited[MAX];
int main() {
    cin.tie(NULL);
    int n;
    cin >> n;
    par[1] = 1;
    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;
    par[1] = 1;
    visited[1] = true;
    q.push(1);
 
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i];
            if (visited[next] == false) {
                visited[next] = true;
                par[next] = now;
                q.push(next);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        cout << par[i] << "\n";
    }
 
}