[Silver / 11725] 트리의 부모 찾기

문제 링크

---

🔷 분류

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

✒️ 문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[100001];
int p[100001];

void dfs(int a) {
	for(int next : adj[a]) {
		if(p[a] == next) continue;
		p[next] = a;
		dfs(next);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
    cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	for(int i = 2; i < n+1; i++) {
		cout << p[i] << "\n";
	}
	return 0;
}