BOJ(백준) 11725 - 트리의 부모찾기

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

---

자료구조(트리), 트리 순회

루트가 1인 트리가 주어지면(트리의 속성 : 정점N개, 간선N-1개), 2번 ~ N번 노드의 부모노드를 출력하는 프로그램을 작성하라

---

시간복잡도 : O(N)

N은 트리의 정점 개수

---

점검해봐야할 부분

- 부모를 기억한 채로 순회

- 루트가 주어지면 방향성도 이미 정해진 것

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/11725.cpp

#include<iostream>
#include<vector>
#define MAX 100005
using namespace std;
vector<int> adj[MAX];
bool visit[MAX];
int parent[MAX], N, a, b;
void go(int idx) {
    visit[idx] = true;
    for (int i = 0; i < adj[idx].size(); i++) {
        int next = adj[idx][i];
        if (!visit[next]) {
            parent[next] = idx;
            go(next);
        }
    }
}
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N - 1; i++) {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    go(1);
    for (int i = 2; i <= N; i++)
        printf("%d\n", parent[i]);
    return 0;
}