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

문제

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

입력

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

출력

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

 

처음에는 각 노드에서 움직이면서 1로 도착하는 부모 노드를 출력하는 것으로 구현했으나 

매 노드별로 visit를 초기화 해야 하고 시간초과 발생

따라서 연결관계를 통해 1부터 내려가면서 이전 노드를 현재 노드의 부모로 삼는것으로 변경

#include <iostream>
#include <vector>
#include<string.h>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;

vector<int> vec[100001];
bool visit[100001];
int parent[100001];

void findParent(int cur)
{
	for (int i = 0; i < vec[cur].size(); i++)
	{
		int next = vec[cur][i];
		if (!visit[next])
		{
			visit[next] = true;
			parent[next] = cur;
			findParent(next);
		}
	}
}

int main() {
	
	ios::sync_with_stdio(false);

	cin.tie(NULL);
	int N;
	cin >> N;
	
	for (int i = 0; i < N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	visit[1] = true;
	findParent(1);
	for (int i = 2; i <= N; i++)
	{
		cout << parent[i] << "\n";
	}
	
}