[알고리즘] 백준 5941번: Meeting Place (C++)

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

5971번: Meeting Place

영어문제였지만 어느 정도 해석이 가능했기에 풀 수 있었다.

1) 노드의 개수와 쿼리의 개수가 주어진다.

2) 2 ~ n까지 부모 노드가 무엇인지 주어진다.

3) m번 동안 a와 b의 LCA를 찾아라.

시간 복잡도는 O(n * m) = O(1000 * 1000)으로 기본적인 LCA를 돌려서 구할 수 있었다.

다른 점은 애초에 입력에서 parent노드가 주어지기 때문에 tree 전처리를 할 때, 부모 노드는 할당해줄 필요가 없었다.

>> level만 갱신해주었다.

[AC 코드]

#include <iostream>
#include <vector>
#define MAX (1000 + 1)
using namespace std;

int parent[MAX];
int level[MAX];
vector<int> graph[MAX];
int n, m;

void treeSet(int node, int pNode) {
	level[node] = level[pNode] + 1;
	for (int i = 0; i < graph[node].size(); i++) {
		int child = graph[node][i];
		//if (child == pNode) continue;
		treeSet(child, node);
	}
}

void swap(int* a, int* b) {
	int* temp = a;
	a = b;
	b = temp;
}

int lca(int a, int b) {
	if (level[a] < level[b]) swap(a, b);
	while (level[a] > level[b]) {
		a = parent[a];
	}

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}

	return a;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int v;
		cin >> v;
		graph[v].push_back(i);
		parent[i] = v;
	}
	treeSet(1, 0);
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		cout << lca(a, b) << '\n';
	}
	return 0;
}