[백준] 11437 - LCA

 

문제

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

 

설명

문제 이름부터 나 LCA 문제입니다. 라고 하고 있는 문제

시간 제한도 3초라 O(N)에 대해 돌면서 조상을 구해도 문제 없다.

구현자체는 트리에서 level을 구하고 서로 만날 때 까지 올라가면 된다.

 

parse table에 부모를 저장하면서 O(logN)으로 돌 수 있는데, 이 부분은 나중에 다시...

 

 

코드

#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int N, M;
vector<int> graph[50001];
int level[50001];
int parent[50001];
queue<int> q;
void lca(int a, int b) {
	int av = a;
	int bv = b;
	while (av != bv) {
		if (level[av] < level[bv]) {
			bv = parent[bv];
		}
		else {
			av = parent[av];
		}
	}
	cout << av << "\n";
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; ++i) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	q.push(1);
	level[1] = 1;
	int cnt = 2;
	while (!q.empty()) {
		int qSize = q.size();
		for (int i = 0; i < qSize; ++i) {
			int curr = q.front();
			q.pop();
			for (int k = 0; k < graph[curr].size(); ++k) {
				if (level[graph[curr][k]]) continue;
				q.push(graph[curr][k]);
				level[graph[curr][k]] = cnt;
				parent[graph[curr][k]] = curr;
			}
		}
		cnt++;
	}
	cin >> M;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		lca(a, b);
	}

	return 0;
}