백준/실버
[백준 11725번] 트리의 부모 찾기 (C++)
게임개발기원
2023. 2. 6. 01:28
문제링크 : 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개인 것을 주의해야 한다.