백준[3584] 가장 가까운 최소 공통 조상

문제 설명

문제 링크

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

풀이

LCA(Lowest Common Ancestor) 기본 문제다.

최소 공통 조상은 트리에서 어떤 두 정점이 같은 가장 가까운 조상을 의미한다.

최소 공통 조상을 구하기 위해서 각 노드의 깊이를 저장해 놓는다.

그 후 a, b의 공통 조상을 찾는다고 한다면 a와 b의 깊이를 동일하게 맞춘 후 둘 다 한 칸씩 조상으로 이동하며 서로 같은지 확인하면 조상이 일치한 지 확인할 수 있다.

시간 복잡도는 O(depth)이다.

cf) 이 문제는 단방향 그래프이므로 루트 노드를 따로 찾아줘야 한다.

코드

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

vector<int> v[10004];
int par[10004], lev[10004], check_root[10004];

void make_tree(int s, int prv) {
    par[s] = prv;
    lev[s] = lev[prv] + 1;
    for (auto nxt : v[s]) {
        if (prv != nxt) make_tree(nxt, s);
    }
}

int lca(int a, int b) {
    if (lev[a] < lev[b]) swap(a, b);
    while (lev[a] != lev[b]) a = par[a];
    while (a != b) {
        a = par[a];
        b = par[b];
    }
    return a;
}

void solve() {
    memset(lev, 0, sizeof lev);
    memset(check_root, 0, sizeof check_root);
    int n; scanf("%d", &n);
    for (int i = 0; i <= n; i++) v[i].clear();

    for (int i = 0; i < n - 1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b);
        check_root[b] = 1;
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (!check_root[i]) root = i;
    }
    make_tree(root, 0);
    int a, b; scanf("%d %d", &a, &b);
    printf("%d\n", lca(a, b));
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}