← Назад к графовым алгоритмам

LCA - наименьший общий предок

Поиск ближайшего общего предка двух вершин в дереве

🐍 Python
from math import log2

n, m = map(int, input().split())
G = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

l = int(log2(n)) + 1
P = [[0] * l for _ in range(n)]
V1 = [0] * n
V2 = [0] * n
t = 0

def dfs(h):
    global t
    for i in range(1, l):
        P[h][i] = P[P[h][i - 1]][i - 1]
    t += 1
    V1[h] = t
    for a in G[h]:
        if V1[a] == 0:
            P[a][0] = h
            dfs(a)
    V2[h] = t

def f(a, b):
    return V1[a] <= V1[b] and V2[b] <= V2[a]

def lca(a, b):
    if f(a, b):
        return a
    if f(b, a):
        return b
    
    for i in range(l - 1, -1, -1):
        if not f(P[a][i], b):
            a = P[a][i]
    
    return P[a][0]

dfs(0)

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    print(lca(a, b) + 1)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<vector<int>> P;
vector<int> V1, V2;
int t = 0;
int l;

void dfs(int h) {
    for (int i = 1; i < l; i++) {
        P[h][i] = P[P[h][i - 1]][i - 1];
    }
    t++;
    V1[h] = t;
    for (int a : G[h]) {
        if (V1[a] == 0) {
            P[a][0] = h;
            dfs(a);
        }
    }
    V2[h] = t;
}

bool f(int a, int b) {
    return V1[a] <= V1[b] && V2[b] <= V2[a];
}

int lca(int a, int b) {
    if (f(a, b)) return a;
    if (f(b, a)) return b;
    
    for (int i = l - 1; i >= 0; i--) {
        if (!f(P[a][i], b)) {
            a = P[a][i];
        }
    }
    
    return P[a][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    G.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    l = log2(n) + 1;
    P.assign(n, vector<int>(l, 0));
    V1.assign(n, 0);
    V2.assign(n, 0);
    
    dfs(0);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << lca(a, b) + 1 << "\n";
    }
    
    return 0;
}

Как работает алгоритм LCA?

LCA (Lowest Common Ancestor) — это алгоритм поиска наименьшего (ближайшего) общего предка двух вершин в дереве. Предком вершины считается любая вершина на пути от корня до данной вершины, включая саму вершину.

Основная идея

Алгоритм использует двоичные подъёмы (binary lifting) и времена входа/выхода (DFS-порядок).

Предподсчёт

Функция f(a, b) проверяет, является ли вершина a предком вершины b: V1[a] ≤ V1[b] и V2[b] ≤ V2[a].

Поиск LCA

  1. Если a — предок b, то LCA = a
  2. Если b — предок a, то LCA = b
  3. Иначе поднимаемся по двоичным степеням сверху вниз, чтобы приблизиться к LCA
  4. После подъёма родитель текущей вершины — LCA

Временная сложность: O(n log n) на предподсчёт, O(log n) на запрос.

Пространственная сложность: O(n log n) для хранения предков.

Пример работы

Рассмотрим дерево из 7 вершин:

        1 (корень)
       /|\
      2 3 4
     / \   \
    5   6   7

Вершины: 1-2-5, 1-2-6, 1-3, 1-4-7

Примеры запросов:

Запрос 1: LCA(5, 6) → общий предок 2 (вершина 2)
Запрос 2: LCA(5, 7) → общий предок 1 (корень)
Запрос 3: LCA(2, 4) → общий предок 1
Запрос 4: LCA(3, 3) → сама вершина 3

Пошаговый поиск LCA(5, 7):
  f(5, 7)? 5 — предок 7? Нет
  f(7, 5)? 7 — предок 5? Нет
  Поднимаем 5:
    Проверяем предка 5 на расстоянии 2ⁱ (i=2,1,0)
    На i=2: предок 5 на 4 шага — не подходит
    На i=1: предок 5 на 2 шага — это 1, f(1,7)? Да → не поднимаем
    На i=0: предок 5 на 1 шаг — это 2, f(2,7)? Нет → поднимаем a=2
  После цикла: a=2, родитель 2 = 1 → LCA = 1

Попробовать алгоритм онлайн

Введите дерево и запросы:

Результат появится здесь...