백준 11725번: 트리의 부모 찾기 (C++)

링크

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

풀이방법

해당 문제는 dfs를 이용하여 완전 탐색과, p라는 배열을 만들어서 p[i]=j i의 부모는 j라는 의미를 사용하여 문제를 해결 할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;


int p[100'005];
vector<int> adj[100'005];
int n;

void dfs(int cur)
{
	for (auto nxt : adj[cur])
	{
		if (p[cur] == nxt) continue;
		p[nxt] = cur;
		dfs(nxt);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);

	for (int i = 2; i <= n; i++)
	{
		cout << p[i] << '\n';
	}

}