트리의 부모 찾기 11725

문제

접근 방법

무향 그래프를 방향 그래프로 만드는 문제이다.
1을 기준으로 잡고 방문하지 않은 곳을 차례로 방문해주며 이전의 노드를 부모로 기록해주면 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, n1, n2;
    cin >> N;
    vector<vector<int>> tree(N + 1, vector<int>());
    vector<int> parents(N + 1);
    queue<int> q;
    for (int i = 0; i < N - 1; ++i)
    {
        cin >> n1 >> n2;
        tree[n1].push_back(n2);
        tree[n2].push_back(n1);
    }
    parents[1] = 1;
    q.push(1);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int i : tree[cur])
        {
            if (parents[i])
                continue;
            parents[i] = cur;
            q.push(i);
        }
    }
    for (int i = 2; i <= N; ++i)
    {
        cout << parents[i] << "\n";
    }
}

풀이

BFS, DFS 등을 사용하여 1에서부터 연결된 부분을 방문해주는 문제다. 처음 입력은 무향 그래프이기에 양쪽 노드에 기록해주어야 한다.