[백준 11725] 트리의 부모 찾기

문제 

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

11725번: 트리의 부모 찾기

 

 

문제 분석 

루트 없는 트리가 주어지고 각각 노드의 부모노드가 무엇인지 출력하는 문제이다. 

 

 

알고리즘 설계 

이중 vector을 사용하여 간단한 트리를 만들어준다. 

 

queue에 1을 넣어 큐가 비어있지 않을떄 실행되는 while을 돌려준다. 

 

큐에 있는 노드와 연결된 노드들의 부모 노드를 queue의 처음으로 정해주고, 연결된 노드들을 queue에 넣어준다. 

 

이후 2번째 노드부터 부모노드가 무엇인지 출력한다. 

 

 

코드

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

using namespace std;

int main()
{
	int loop, input1, input2, front;
	cin >> loop;
	vector<vector<int>> graph(loop + 1);
	vector<int> visited(loop + 1, -1);
	queue<int> q;

	for (int i = 1; i < loop; ++i)
	{
		cin >> input1 >> input2;
		graph[input1].push_back(input2);
		graph[input2].push_back(input1);
	}

	q.push(1);

	while (!q.empty())
	{
		front = q.front();
		q.pop();

		for (auto i : graph[front])
		{
			if (visited[i] != -1)
				continue;

			visited[i] = front;
			q.push(i);
		}
	}

	for (int i = 2; i < visited.size(); ++i)
		cout << visited[i] << '\n';
}