[백준] 알고리즘 11725번 - 트리의 부모 찾기 문제

트리의 부모 찾기 문제

소스코드

#include <bits/stdc++.h>
using namespace std;
vector<int> v[100001];
bool check[100001];
int p[100001];
void dfs(int x) {
	check[x] = true;
	int size = v[x].size();
	for (int i = 0; i < size; i++) {
		if (check[v[x][i]] == false) {
			p[v[x][i]] = x;
			dfs(v[x][i]);
		}
	}
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int n;
   cin >> n;
   for (int i = 1; i < n; i++) {
	   int x, y;
	   cin >> x >> y;
	   v[x].push_back(y);
	   v[y].push_back(x);
   }
   dfs(1);
   for (int i = 2; i <= n; i++) {
	   cout << p[i] << "\n";
   }
}

 

해결방법

트리는 한 정점을 방문하면 모든 정점을 조사할 수 있다.

2번 노드의 부모를 차례로 출력하기 위해서 P배열에 저장후 출력해주면된다.