LCA (Lowest Common Ancestor)

코드

LCA 2 (https://www.acmicpc.net/problem/11438) 에 대한 소스

#include <stdio.h>
#include <vector>

#define NCNT 100000
#define LGN 20

using namespace std;

int n, dy[NCNT+1][LGN+1], lv[NCNT+1], visit[NCNT+1];
vector<int> g[NCNT+1];

void dfs(int node)
{
    int i, j;
    visit[node] = 1;
    for ( i = 0; i < g[node].size(); i++ ) {
        int u = g[node][i];
        if ( visit[u] ) continue;
        lv[u] = lv[node]+1;
        dy[u][0] = node;
        for ( j = 1; j <= LGN; j++ )
            dy[u][j] = dy[dy[u][j-1]][j-1];
        dfs(u);
    }
}

int lca(int a, int b)
{
    int i;

    if ( lv[a] < lv[b] ) swap(a, b);
    for ( i = LGN; i >= 0; i-- )
        if ( (1 << i) <= lv[a] - lv[b] )
            a = dy[a][i];
    if ( a == b )
        return a;
    for ( i = LGN; i >= 0; i-- )
        if ( dy[a][i] != dy[b][i] )
            a = dy[a][i], b = dy[b][i];
    return dy[a][0];
}

int main()
{
    int m, a, b, i, j;

    scanf("%d", &n);
    for ( i = 1; i < n; i++ ) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }

    lv[1] = 1;
    dfs(1);

    scanf("%d", &m);
    while( m-- ) {
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }
}

정리

  • 레벨 기록하기
    • 각 노드가 트리상에 레벨이 몇인지를 기록해야 한다.
  • 상향식 테이블 만들기
    • dy[v][i] : 정점 v 에서 2^i 번째 부모 번호
    • 점화식은 dy[v][i] = dy[dy[v][i-1]][i-1] 임을 알 수 있다.
    • 2^i 번째 부모가 없으면 0 이라 생각한다.
  • 최단 공통 조상 찾기 (lca)
    • 두 노드의 level 을 맞춘다.
      • i=lgN...0, 레벨 차이가 2^i(1 << i) 보다 크면, i 만큼 부모로 이동한다. (최총적으로 같아진다)
    • 만약 두 노드가 같으면, 해당 노드가 조상 노드이다.
    • 두 노드가 같아질 때 까지 부모로 이동한다.
      • i=lgN...0, i 만큼 이동한 부모가 다르면, i 만큼 부모로 이동한다. (최종적으로 같아진다)
    • 이 시점에서 두 노드의 부모는 같은 조상이다. (dy[a][0] == dy[b][0])
  • 이 문제는 세그먼트 트리를 이용해서 풀 수도 있다. (트리를 펴서 푸는 방법, 종만북에서 나옴)

관련 문제

참고 자료

results matching ""

    No results matching ""