[백준]Baekjoon11725 (트리의 부모 찾기)

문제 링크 : https://www.acmicpc.net/problem/11725

#include <iostream>
#include <vector>
#include <queue>

#define SIZE 100001

using namespace std;

vector<int> tree[SIZE]; //주어진 트리
int ans[SIZE]; //ans[i]는 i 노드의 값을 의미
bool check[SIZE]; //방문한 노드를 check

void function()
{
	queue<int> q;
	q.push(1); // node 1 부터 시작하므로 큐에 push
	check[1] = true; //1번 노드는 방문했으므로 check
	while (!q.empty())
	{
		int x = q.front();
		q.pop(); //큐에서 하나 꺼냄
		
		for (int i = 0; i < tree[x].size(); i++)
		{
			if (!check[tree[x][i]]) //만약 이어진 노드가 방문한 노드가 아니라면
			{
				int next = tree[x][i];
				ans[next] = x; //next 노드의 부모는 x
				check[next] = true; //next노드를 방문했으므로 true로 설정
				q.push(next); //next 노드를 큐에 집어넣는다.
			}
		}
	}
}
int main()
{
	int N;
	scanf("%d", &N);
	int node_num = N--;
	int u, v;
	while (N--)
	{
		scanf("%d %d", &u, &v);
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	function();
	for (int i = 2; i <= node_num; i++)
		printf("%d\n", ans[i]);
}