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

문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
.
.

풀이

루트노드를 1로 가정하는 것이니,
부모 노드를 기록해주면서 dfs를 진행한다.

#include <iostream>
#include <vector>
using namespace std;

// 트리 정보 저장
vector<int> map[100001];
// 방문 정보 저장
vector<int> ch(100001);
vector<int> res(100001);

void DFS(int n, int parent)
{
	if (ch[n] == 1)
	{
		return;
	}
	// 방문 표시
	ch[n] = 1;
	res[n] = parent;
	// 자식 노드들 방문하기 시작
	for (int i = 0; i < map[n].size(); i++)
	{
		// 방문 안한 노드
		if (ch[map[n][i]] == 0)
		{
			DFS(map[n][i], n);
		}
	}

}

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

	int N, a, b;
	cin >> N;

	// 입력받기
	for (int i = 0; i < N-1; i++)
	{
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	DFS(1, 0);

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

	return 0;
}