11725번: 트리의 부모 찾기

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

$O(n)$

#include<cstdio>
#include<vector>
using namespace std;
int n, p[100001];
vector<int> adj[100001];
void f(int h) {
    for (auto it : adj[h]) if (p[h] ^ it) p[it] = h, f(it);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    for (int i = 2; i <= n; i++) printf("%d\n", p[i]);
    return 0;
}