Lowest Common Ancestor

최소 공통 조상을 O(logn)에 찾기위한 알고리즘이다. O(logn)에 찾기 위해서 parent 배열을 만드는데 이 배열을 만드는데 O(nlogn)의 시간이 필요하다. 그 이후에 쿼리에서는 O(logn)에 동작한다.

implementaion

plaintext

#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> adj;
vector<vector<int>> parent;
vector<int> level;

void dfs(int node) { //O(v + e) => O(n) this case (because it's tree)
    for(auto near : adj[node]) {
        if(level[near] == 0) {
            parent[near][0] = node;
            level[near] = level[node] + 1;
            dfs(near);
        }
    }
}

void init() { //o(nlogn)
    int n = adj.size();
    int m = parent[0].size();

    for(int p = 0; p < m; p++) {
        for(int node = 1; node < n; node++) {
            if(parent[node][p] != -1) {
                parent[node][p + 1] = parent[parent[node][p]][p];
            }
        }
    }
}

int lca(int u, int v) { //o(logn)
    if(level[u] < level[v]) swap(u, v);
    int diff = level[u] - level[v];
    int ma = parent[0].size();

    for(int j = 0; diff; j++) {
        if(diff & 1) u = parent[u][j];
        diff /= 2;
    }

    if(u != v) {
        for(int j = ma - 1; j >= 0; j--) {
            if(parent[u][j] != -1 and parent[u][j] != parent[v][j]) {
                v = parent[v][j];
                u = parent[u][j];
            }
        }
        u = parent[u][0];
    }
    return u;
}

int main() {
    vector<vector<int>> edges = {{1, 2},{2, 3},{5, 6},{4, 2},{7, 5},{1,5}};
    int n = 7;
    level = vector<int>(n + 1, 0);
    adj = vector<vector<int>>(n + 1);
    parent = vector<vector<int>>(n + 1,vector<int>(log2(n) + 1, -1));

    for(auto e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    level[1] = 1;
    dfs(1);
    init();
    cout<<lca(3, 5)<<endl;

    return 0;
}