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

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

입력

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

출력

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

풀이

무조건 이진트리라는 보장이 없다.
그걸 염두하고 풀면된다.
추가 정답 배열을 만들고

dfs에서

   if (result[i] == 0)
        {
            result[i] = n;
            bfs(i);
        }

다음 루프 전에 현재 정답 배열 i에 돌리고 있는 n값을 넣어주면
바로 트리의 부모의 값이 된다.

그 후 정답배열을 출력하면
각각의 배열원소가 자신의 부모 노드의 번지이다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int>>Arr;
vector<int>result;
void bfs(int n)
{
    for (auto i : Arr[n])
    {
        int k = i;
        if (result[i] == 0)
        {
            result[i] = n;
            bfs(i);
        }
    }

 }


int main(void)
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    Arr.resize(n + 1);

    result.resize(n + 1);
   

    for (int i = 0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        Arr[a].push_back(b);
        Arr[b].push_back(a);
    }
    bfs(1);
    for (int i = 2; i <= n; i++)
    {
        cout << result[i] << "\n";
    }
  
}