LCA 최소 공통 조상

최소 공통 조상을 찾는 알고리즘입니다.

두 정점이 만나는 최초 부모 정점을 찾으면 됩니다. 

 

예시)13번과 15번의 공통 조상 노드는 5번노드이다.

예시) 13번과 11번 노드의 공통조상은 1번노드이다. 

 

 

 

LCA 알고리즘을 푸는 방법은 인풋(트리의 형태)가 어떻게 주어지느냐에 따라 다르지만 기본적으로 root노드와 자식노드만 알고있다고 가정해보겠습니다.

LCA을 풀기위한 가장 효율적인 방법은 Sparse Tree을 사용하는 것입니다.

이 방법은 우선 DFS을 이용하여 Depth(해당 레벨에 어떤 노드들이 존재하는지 알려주는 배열), Parent(해당 노드의 부모 노드를 알려주는 배열)을 구합니다. 

 

const int MAX = 100001; // 최대 노드 수
const int LOG = 17; // 2^17은 131072로, 100000보다 큼
vector<int> adj[MAX]; // 인접 리스트
int depth[MAX]; // 각 노드의 깊이
int parent[MAX][LOG]; // Sparse Table. parent[i][j]는 노드 i의 2^j번째 조상

// DFS를 이용하여 각 노드의 깊이와 첫 번째 부모를 설정
void dfs(int v, int p) {
    depth[v] = depth[p] + 1;
    parent[v][0] = p;
    for (int u : adj[v]) {
        if (u != p) dfs(u, v);
    }
}

// Sparse Table을 채움
void preprocess(int root, int n) {
    dfs(root, root);
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            parent[i][j] = parent[parent[i][j-1]][j-1];
        }
    }
}

// LCA를 찾는 함수 이전에 preprocess함수를 한번 돌려야 함
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 깊이를 맞춤
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[u] - depth[v] >= (1 << i)) {
            u = parent[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}

 

쿼리당 O(logN)이고 전처리과정은 O(NlogN)입니다.