백준 11725 c++ 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

---

문제

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

입력

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

출력

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

---

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

int N;
vector<int> rel[100001];//관련성을 나타내는 배열
int pre[100001];//이전 노드(여기서는 부모 노드)
bool visit[100001];

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	visit[start] = true;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < rel[x].size(); i++)
		{
			if (visit[rel[x][i]])
				continue;
			pre[rel[x][i]] = x;
			visit[rel[x][i]] = true;
			q.push(rel[x][i]);
		}

	}
}

int main()
{
	cin >> N;
	for (int i = 1; i < N; i++)
	{
		int x, y;
		cin >> x >> y;
		rel[x].push_back(y);
		rel[y].push_back(x);
	}
	bfs(1);
	for (int i = 2; i <= N; i++)
	{
		cout << pre[i] << '\n';
	}
}