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

문제링크 : https://www.acmicpc.net/problem/11725

 

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

int n;
int arr[100001];        //트리의 부모 담을 배열
vector<int> v[100001];  //해당 값에 연결된 값들을 갖는 배열

void dfs(int num)
{
	for (int i = 0; i < v[num].size(); i++)
	{
		if (arr[num] == v[num][i]) { continue; } //num은 현재 값, v[num][i]는 next 값을 가리킴. 둘이 같으면 건너뜀
		arr[v[num][i]] = num;  //부모 노드 저장
		dfs(v[num][i]);        //다음 값에 연결된 값들 탐색
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int x, y;
		cin >> x >> y;          //두 정점 입력 (ex 1, 4)
		v[x].push_back(y);      //v[1] = 4
		v[y].push_back(x);      //v[4] = 1 (값 연결)
	}

	dfs(1);                     //루트는 1

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

}

입력값이 n개가 아닌, n-1개인 것을 주의해야 한다.