[백준][bfs] 트리의 부모 찾기 11725 c++구현

목차

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

11725번: 트리의 부모 찾기

제목

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

이진 트리가 아니기 때문에 인접리스트를 만들어 bfs탐색을 통해 해결해 보았다.

 

 

 

 

코드 구현

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

using namespace std;

vector<int>tree[100000];
vector<bool>visit(100000, false);
vector<int>parent(100000, 0);  //부모를 저장할 배열

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 < tree[x].size(); i++) {
			int y = tree[x][i];
			if (!visit[y]) {
				q.push(y);
				visit[y] = true;
				parent[y] = x;
			}
		}
	}

}

int main() {
	int n, node1, node2, i, j, k=2;
	cin >> n;
	for (i = 1; i <= n-1; i++) {
		cin >> node1 >> node2;
		tree[node1].push_back(node2);  //양방향 그래프로 만들어 준다.
		tree[node2].push_back(node1);
	}
	bfs(1);

	for (i = 2; i <= n; i++) {
		cout << parent[i]<<"\n";     
	}
}