코드 복사/붙여넣기 하는 당신이 아름답습니다.

11437 : LCA

풀이

naive한 풀이!

dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤,

u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에

두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다.

코드

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const int n_ = 5e4 + 3;

int n, m;
int dph[n_], pnt[n_];
vector<int> gph[n_];

inline void dfs(int now, int cnt) {
	dph[now] = cnt++;
	for (auto nxt : gph[now]) {
		if (!dph[nxt]) dfs(nxt, cnt), pnt[nxt] = now;
	}
}

int main() {
	int a, b, i;
	scanf("%d", &n);
	while (--n) {
		scanf("%d %d", &a, &b);
		gph[a].push_back(b);
		gph[b].push_back(a);
	}
	dfs(1, 1);
	scanf("%d", &m);
	while (m--) {
		scanf("%d %d", &a, &b);
		if (dph[a] < dph[b]) swap(a, b);
		while (dph[a] != dph[b]) a = pnt[a];
		while (a != b) a = pnt[a], b = pnt[b];
		printf("%d\n", a);
	}
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-10 12:20

Read more posts by this author