백준 11725번: 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

이번에는 노드의 부모노드 번호를 구하는 문제이다. 나는 이 문제를 DFS로 풀었고 탐색을 진행하면서 각 노드에 해당하는 부모를 부모노드 배열에 넣었다.

그래서 한번의 탐색으로 각 노드의 부모를 저장한 배열을 구할 수 있다.

#include<iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
#pragma warning(disable : 4996)
vector<int> d[100020];             //각 인덱스 별로 연결된 노드 배열
bool check[100020];                //방문 했는지 배열
int parent[100020];                //부모노드 배열
void dfs(int a) {                     //dfs탐색
	check[a] = true;
	for (int i = 0; i < d[a].size(); i++) {
		int next = d[a][i];
		if (check[next] == false) {
			parent[next] = a;               //부모자식 인덱스에 부모값 대입
			dfs(next);          
		}
		
	}
}
int main() {
	int n;
	cin >> n;
	int t = n - 1;
	while (t--) {
		int a, b;
		cin >> a >> b;
		d[a].push_back(b);
		d[b].push_back(a);
	}
	dfs(1);
	parent[1] = 0;             //1은 루트로 부모가 없으므로 0대입
	for (int i = 2; i <= n; i++) {
		cout << parent[i] << '\n';
	}
	return 0;
}