[백준] LCA 2 11438번 C++ 풀이

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

11438번: LCA 2

 

전체 코드

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> v[100001];
int parent[100001][17]; // log2(100000) = 16.61 -> 17
int depth[100001];
int N,M;
void DFS(int cur)
{
	for (int i = 0; i < v[cur].size(); i++)
	{
		int next = v[cur][i];
		if (depth[next] == -1)
		{
			parent[next][0] = cur;
			depth[next] = depth[cur] + 1;
			DFS(next);
		}

	}

}

void connect()
{
	for (int k = 1; k < 17; k++)
	{
		for (int cur = 1; cur <= N; cur++) // cur을 2부터해도 될거같은데
			parent[cur][k] = parent[parent[cur][k - 1]][k-1];
	}
}

int LCA(int a, int b) {

	// 깊이가 더 큰게 a로 오게
	if (depth[a] < depth[b])
	{
		int temp = a;
		a = b;
		b = temp;
	}

	int diff = depth[a] - depth[b];
	for (int i = 0; diff != 0; i++)
	{
		if (diff % 2 == 1)
			a = parent[a][i];
		diff /= 2;
	}

	if (a != b)
	{
		for (int i = 16; i >= 0; i--)
		{
			if (parent[a][i] != -1 && parent[a][i] != parent[b][i])
			{
				a = parent[a][i];
				b = parent[b][i];
			}
		}

		a = parent[a][0];
	}
	return a;
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int a, b;
	cin >> N;
	fill(depth, depth + N + 1, -1);
	depth[1] = 0;// root 노드

	for (int i = 0; i < N-1; i++)
	{
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	DFS(1);
	connect();

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		cout << LCA(a, b) << "\n";
	}
}

 

해당 LCA 알고리즘에 관하여는 알고리즘으로 카테고리에 따로 작성하도록 하겠습니다.

 

설명 -> https://non-stop.tistory.com/132