[BOJ] 11437번 LCA (C++)

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

11437번: LCA

 

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

int parent[50001];
int depth[50001];
bool visited[50001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	vector<int> node[50001];
	for(int i = 0; i < n - 1; i++){
		int x, y;
		cin >> x >> y;
		node[x].push_back(y);
		node[y].push_back(x);
	}
	
	queue<int> q;
	q.push(1);
	visited[1] = true;
	
	while(!q.empty()){
		int x = q.front();
		q.pop();
		
		for(int i = 0; i < node[x].size(); i++){
			if(!visited[node[x][i]]){
				depth[node[x][i]] = depth[x] + 1;
				visited[node[x][i]] = true;
				parent[node[x][i]] = x;
				q.push(node[x][i]);
			}
		}
	}

	int m;
	cin >> m;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		if(depth[x] > depth[y]){
			int tmp = x;
			x = y;
			y = tmp;
		}
		while(depth[x] != depth[y]){
			y = parent[y];
		}
		while(x != y){
			x = parent[x];
			y = parent[y];
		}
		cout << x << '\n';
	}
	return 0;
}

 

부모와 자식 관계가 주어지지 않고, 루트 노드가 1이라는 정보만 주어졌기 때문에 깊이 정보를 담을 배열을 따로 만들어서 해결했다. 

두 노드 중 깊이가 더 깊은 것을 두 노드의 깊이가 같아질 때까지 부모와 교환하며 거슬러 올라온다. 두 노드의 깊이가 같아지면 공통 조상을 만날 때까지 위로 거슬러 올라간다.