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

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

BFS로 순회하면서 풀었다. 벡터 배열을 static으로 선언한 이유는 배열의 크기가 너무 커서 비주얼 스튜디오에서 돌리면 자꾸 런타임에러가 나면서 종료되어서 static으로 선언해서 힙에 할당하도록 해줬다.

제출할 때는 static 빼도 정답으로 나왔다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	static vector<int> graph[100001];
	int from, to;
	for (int i = 0; i < n - 1; i++) {
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	vector<bool> visited(n + 1, false);
	vector<int> parent(n + 1, -1);
	queue<int> q;
	q.push(1);
	parent[1] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (!visited[cur]) {
			visited[cur] = true;
			for (int i = 0; i < graph[cur].size(); i++) {
				if (parent[graph[cur][i]] == -1) {
					parent[graph[cur][i]] = cur;
					q.push(graph[cur][i]);
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		cout << parent[i] << '\n';
	}
	return 0;
}