[8일차] 그래프1 D - 11438: LCA 2

플래티넘 Ⅴ

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 17
using namespace std;
int N, M;

vector<int> adjList[100001];//dfs 하려고 있는거임
bool visit[100001] = { 0, };
int depth[100001] = { 0, };
int dp[100001][MAX + 1] = { 0, };

//int node, int depth
void dfs(int n, int d) {
	visit[n] = true;
	depth[n] = d;

	for (int i = 0; i < adjList[n].size(); i++) {
		int nextNode = adjList[n][i];
		if (visit[nextNode]) continue;
		dp[nextNode][0] = n;
		dfs(nextNode, d + 1);
	}
}

//y의 depth가 더 깊다고 가정
int lca(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	//y를 x와 같은 깊이로 올려주기
	for (int i = MAX; i >= 0; i--) {
		//범위 안에 들어오면 y 올려주기
		if (depth[y] - depth[x] >= (1 << i))
			y = dp[y][i];
	}
	//올려주는거 끝났을 때 x랑 y가 같다면 -> x가 y의 조상인 경우
	if (x == y) return x;

	//MAX에서 시작해야함... 젤 높은얘 찾는거라
	for (int i = MAX; i >= 0; i--) {
		//(원래 엄청 큰 숫자로 하면 루트 넘어가서 둘 조상이 0으로 같음)
		//x의 i번쨰 조상과 y의 i번째 조상이 다르다면
		if (dp[x][i] != dp[y][i]) {
			//올라가
			x = dp[x][i];
			y = dp[y][i];
		}
	}
	//올라갔으면 x, y 얘네의 부모노드가 lca임
	return dp[x][0];
}

int main() {
	scanf("%d", &N);
	int u, v;
	for (int i = 1; i < N; i++) {
		scanf("%d%d", &u, &v);
		adjList[u].push_back(v);
		adjList[v].push_back(u);
	}

	//1(루트)부터 시작, 루트의 depth는 1
	dfs(1, 1);
	//dp
	for (int ith = 1; ith < MAX; ith++) {//1번쨰 조상부터.. MAX조상까지
		for (int node = 1; node <= N; node++) {
			//N개의 노드들에 대해서...i번째 조상까지 구한다
			//depth 하나 적은 조상의 ith-1 조상이다
			dp[node][ith] = dp[dp[node][ith - 1]][ith - 1] ;
		}
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d\n", lca(x, y));
	}
}

 

최소공통조상 (LCA) 

 

필요한 자료구조: depth, dp, adjList(dfs땜에), visit(dfs땜에)

 

풀려면 depth랑 dp가 필수로 필요한데 depth를 구하려면 dfs(또는 bfs)가 필요하다

근데 dfs하려면 adjList랑 visit이 필요하다

 

lca 알고리즘 자체는 for문 두 개면 된다

1. 노드 u와 v를 같은 depth로 만들어주는 for문 이랑

2. depth가 같아진 u와 v를 lca의 child로 만들어주는 for문

 

끝!

 

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

3584번: 가장 가까운 공통 조상

 

루트가 없는 트리도 존재하나?

아니라고 할때 -> 루트를 안알려주면 찾아야겠다

-> lca 알고리즘에서는 루트로부터의 depth가 중요하다