백준 11725 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

각 노드의 부모를 찾는 문제이다. 예제 입력을 보면 누가 부모이고 자식인지 알 수 없다. 그래서 각 노드를 서로 넣어주어야 한다. 

 

for(int i = 1; i < N; i++){
		scanf("%d %d", &firstPoint, &secondPoint);
		map[firstPoint].push_back(secondPoint);
		map[secondPoint].push_back(firstPoint);
	}

 

이 문제는 1을 상위노드로 지정해주었기 때문에 1을 시작으로 연결된 노드들을 탐색하는 bfs 방법을 사용하면된다. 

그리고 각 결과값을 저장할 때 이미 상위 노드를 찾았을 때는 큐에 넣어 주지 않는다. 

 

물론 dfs로도 찾을 수 있다.

 

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

vector <int> map[100002];
int result[100002];
int N;
queue <int> qu;

void input();
void bfs();
void output();

int main(){
	input();
	bfs();
	output();
}

void input(){
	scanf("%d", &N);
	int firstPoint, secondPoint;
	for(int i = 1; i < N; i++){
		scanf("%d %d", &firstPoint, &secondPoint);
		map[firstPoint].push_back(secondPoint);
		map[secondPoint].push_back(firstPoint);
	}
}

void bfs(){
	qu.push(1);

	while(!qu.empty()){
		int starter = qu.front();
		qu.pop();
		for(int i = 0; i < map[starter].size(); i++){
			if(result[map[starter][i]] == 0){
				result[map[starter][i]] = starter;
				qu.push(map[starter][i]);
			}
		}
	}
}

void output(){
	for(int i = 2; i <= N; i++ )
		printf("%d\n", result[i]);
}