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

 

연결 노드들을 그려보면 다음과 같은 그림이 나옵니다.

 

풀이)

2번부터 n번까지의 노드들의 부모들을 찾아야합니다.

이때 저는 트리를 인접리스트로 구현하였으며 BFS가 익숙하기 때문에 노드들을 찾는 과정은 bfs를 사용하였으며,

다음 노드를 찾고 해당 노드의 부모를 배열에 저장해 주는 방식으로 구현하였습니다.  

 

코드)

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

const int MAX = 100'001;

vector<int>tree[MAX];
bool visited[MAX]{};
int arr[MAX]{};

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (not q.empty()) {
		int nx = q.front();
		q.pop();

		for (int node : tree[nx]) {
			if (not visited[node]) {
				q.push(node);
				visited[node] = true;
				arr[node] = nx;
			}
		}
	
	}



}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n-1; ++i) {
		int u, v;
		cin >> u >> v;
		
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	bfs(1);

	for (int i = 2; i <= n; ++i) {
		cout << arr[i] << '\n';
	}

}