Lowest common ancestor(LCA)

LCA

트리에서 서로 다른 두 노드에 대해 루트노드에서 가장 멀리 있는 공통 조상을 LCA라고 합니다.

위의 그림에서 검은색 노드의 LCA는 빨간색 입니다.

 

LCA를 찾는 방법은

1. 두 노드의 dept를 맞춘다.

2. 두 노드가 같아질때까지 계속 위로 올라간다.

 

2단계롤 나눌수 있습니다.

가장 쉽게 구현할수 있는 방법은 하나씩 올라가는 것입니다. 이 경우엔 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다.

 

더 빠르게 구현하기 위해서 '희소테이블' 이라는 테크닉을 이용할 수 있습니다.

즉 하나씩 올라가는 것이 아니라 가능한 최대한 멀리 올라가는 것이지요.

예를들어 두 노드 A, B의 LCA인 C노드의 깊이가 3이고

A의 깊이는 100, B의 깊이는 200 이라고 하면, 하나씩 올라가는것은 너무 정직하게 올라가는 것이죠.

한칸이 아닌 여러칸씩 올라가게 되면 훨씬더 빠르게 LCA를 찾을 수 있습니다.

희소테이블에

parent[i][j] : i노드의 2^j위에 있는 노드

의 규칙으로 저장하고 올라가게 된다면 A, B노드의 깊이를 같게 만드는데 100번의 연산이 아닌 3번의 연산으로 해결할 수 있습니다.(low하게 올라가면 하나씩 올라가 100번의 시도를 해야 하지만 희소테이블을 사용하면 100의 이진수 표현 1100100 에서 유효한 1이 3개라 3번이면 올라갈 수 있습니다.) 즉 최악의 경우에도 O(lgn)이면 LCA를 찾을 수 있습니다.

 

구현은 밑의 문제로 대신하겠습니다.

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

11438번: LCA 2

 

 

//11438 - LCA 2
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<vector<int>> adj;
vector<bool> visit;
int parent[100001][18];
int dept[100001];
 
void dfs(int here)
{
    for(int i = 0; i<adj[here].size(); ++i)
    {
        int there = adj[here][i];
        if(!visit[there])
        {
            visit[there] = true;
            dept[there] = dept[here] + 1;
            parent[there][0] = here;
            dfs(there);
        }
    }
}
 
void init()
{
    cin >> N;
    adj = vector<vector<int>>(N+1);
    visit = vector<bool>(N+1, false);
    int x, y;
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j < 18; ++j)
            parent[i][j] = -1;
    parent[1][0] = 1;
    dept[1] = 0;
    for (int i = 0; i < N - 1; ++i)
    {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    visit[1] = true;
    dfs(1);
    for (int j = 1; j < 17; ++j)
        for (int i = 1; i <= N; ++i)
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
    cin >> M;
}
 
int lastOneBit(int u)
{
    int ret = 0;
    while (u % 2 == 0)
    {
        u /= 2;
        ++ret;
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int u, v;
    for (int i = 0; i < M; ++i)
    {
        cin >> u >> v;
        if (dept[u] < dept[v])
            swap(u, v);
        int gap = dept[u] - dept[v];
        while (gap)
        {
            u = parent[u][lastOneBit(gap)];
            gap &= (gap - 1);
        }
 
        while (u != v)
        {
            for (int j = 17; j >= 0; --j)
                if (parent[u][j] != -1 && parent[u][j] != parent[v][j])
                {
                    u = parent[u][j], v = parent[v][j];
                    break;
                }
            u = parent[u][0], v = parent[v][0];
        }
 
        cout << u << "\n";
    }
}