11725_트리의 부모 찾기

▶ 실버 2 (트리)

문제

풀이

처음엔 queue<pair<int, int>> 를 선언하여 parent 배열이 다 채워질 때까지 노드 쌍을 queue에 다시 삽입하는 방법을 생각했다. 하지만 O(N^2) 시간복잡도로 시간 초과가 났다.

그래서 bfs, dfs 중 bfs를 이용하여 풀었다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 100001
using namespace std;

int n;
vector<int> tree[MAX];
queue<int> q;
bool visited[MAX];
int parent[MAX];

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

	while(!q.empty()) {
		int start = q.front();
		q.pop();
		visited[start] = true;
		while (!tree[start].empty()) {
			int v = tree[start].back();
			tree[start].pop_back();

			if (!visited[v] && parent[v] == 0) {
				parent[v] = start;
				q.push(v);
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;

		tree[b].push_back(a);
		tree[a].push_back(b);
	}
	bfs();
	for (int i = 2; i <= n; i++) {
		cout << parent[i] << "\n";
	}
}