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

풀이 방법 : DFS

입력으로 주어지는 트리의 노드 간의 연결정보를 다 저장해 준 후 시작점을 1로 두고 DFS를 돌려주면서 부모 정보들을 갱신해나가면 된다.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool check[100001] = {};

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

	int N;
	cin >> N;

	vector<vector<int>> vecNode(N + 1);

	for (int i = 1; i < N; ++i)
	{
		int Src, Dest;
		cin >> Src >> Dest;

		vecNode[Src].push_back(Dest);
		vecNode[Dest].push_back(Src);
	}

	vector<int> vecParent(N + 1);

	stack<int> sNode;
	sNode.push(1);
	check[1] = true;

	while (!sNode.empty())
	{
		int Parent = sNode.top();
		sNode.pop();

		int Size = vecNode[Parent].size();

		for (int i = 0; i < Size; ++i)
		{
			int Child = vecNode[Parent][i];

			if (check[Child])
				continue;

			check[Child] = true;
			vecParent[Child] = Parent;

			sNode.push(Child);
		}
	}

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