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

11725번: 트리의 부모 찾기

dfs를 이용한 문제이다. dfs를 통해 입력받은 연결된 노드들을 순차적으로 순회하며 parent 배열에 현재 노드를 저장해주었다. 간단하게 풀 수 있었던 문제였다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v[100001];
int parent[100001];
bool check[100001];

void dfs(int now) {
	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];

		if (check[next]) continue;

		check[next] = true;
		parent[next] = now;
		dfs(next);
	}
}

void solution() {
	check[1] = true;
	dfs(1);

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	int a, b;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	solution();
	
	return 0;
}