E047. Lowest common ancestor. Нахождение за O (log N) (метод двоичного подъёма)

e-maxx algorithm original: C/C++ #algorithm #emaxx #graph #lca #tree

题目文本会按所选界面语言从俄语翻译；代码保持不变。

Static

Источник: e-maxx.ru/algo, страница PDF 141.

Пусть given 树 G. На 输入 поступают запросы вида (V1, V2), для каждого запроса it is required find их наименьшего общего предка, т.е. вершину V, которая лежит на пути от корня до V1, на пути от корня до V2, и из всех таких вершин следует выбирать самую нижнюю. Иными словами, искомая vertex V - предок и V1, и V2, и среди всех таких общих предков выбирается нижний. Очевидно, что Lowest common ancestor вершин V1 и V2 - это их общий предок, лежащий на кратчайшем пути из V1 в V2. В частности, на示例, если V1 является предком V2, то V1 является их наименьшим общим предком. На английском эта 题目 называется задачей LCA - Least Common Ancestor. Здесь будет рассмотрен 算法, который пишется намного быстрее, чем описанный здесь. Asymptotic complexity полученного 算法а будет равна: препроцессинг за O (N log N) и ответ на каждый запрос за O (log N).

算法

Предпосчитаем для каждой вершины её 1-го предка, 2-го предка, 4-го, и т.д. Обозначим этот 数组 через P, т.е. P[i][j] - это 2j-й предок вершины i, i = 1..N, j = 0..•logN•. Также для каждой вершины найдём времена захода в неё и 输出а поиска в глубину (см. "Depth-first search") - это нам понадобится, чтобы определять за O (1), является ли одна vertex предком другой (не обязательно непосредственным). Такой препроцессинг можно выполнить за O (N log N). Пусть теперь поступил очередной запрос - пара вершин (A,B). Сразу проверим, не является ли одна vertex предком другой - в таком случае она и является результатом. Если A не предок B, и B не предок A, то будем подниматься по предкам A, пока не найдём самую высокую (т.е. наиболее близкую к корню) вершину, которая ещё не является предком (не обязательно непосредственным) B (т.е. такую вершину X, что X не предок B, а P[X][0] - предок B). При этом находить эту вершину X будем за O (log N), пользуясь 数组ом P. Опишем этот процесс подробнее. Пусть L = •logN•. Пусть сначала I = L. Если P[A][I] не является предком B, то присваиваем A = P[A][I], и уменьшаем I. Если же P[A][I] является предком B, то просто уменьшаем I. Очевидно, что когда I станет меньше нуля, vertex A как раз и будет являться искомой вершиной - т.е. такой, что A не предок B, но P[A][0] - предок B. Теперь, очевидно, ответом на LCA будет являться P[A][0] - т.е. наименьшая vertex среди предков исходной вершины A, являющаяся также и предком B. Asymptotic complexity. Весь 算法 ответа на запрос состоит из изменения I от L = •logN• до 0, а также проверки на каждом шаге за O(1), является ли одна vertex предком другой. Следовательно, на каждый запрос будет найден ответ за O (log N).

实现

int n, l;

vector < vector<int> > g;

vector<int> tin, tout;

int timer;

vector < vector<int> > up;

void dfs (int v, int p = 0) {

tin[v] = ++timer;

up[v][0] = p;

for (int i=1; i<=l; ++i)

up[v][i] = up[up[v][i-1]][i-1];

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (to != p)

dfs (to, v);

}

tout[v] = ++timer;

}

bool upper (int a, int b) {

return tin[a] <= tin[b] && tout[a] >= tout[b];

}

int lca (int a, int b) {

if (upper (a, b))  return a;

if (upper (b, a))  return b;

for (int i=l; i>=0; --i)

if (! upper (up[a][i], b))

a = up[a][i];

return up[a][0];

}

int main() {

... чтение n и g ...

tin.resize (n), tout.resize (n), up.resize (n);

l = 1;

while ((1<<l) <= n)  ++l;

for (int i=0; i<n; ++i)  up[i].resize (l+1);

dfs (0);

for (;;) {

int a, b; // текущий запрос

int res = lca (a, b); // ответ на запрос

} }

C# 解法

自动草稿，提交前请检查

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int n, l;
    vector < List<int> > g;
    List<int> tin, tout;
    int timer;
    vector < List<int> > up;
    void dfs (int v, int p = 0) {
            tin[v] = ++timer;
            up[v][0] = p;
            for (int i=1; i<=l; ++i)
                    up[v][i] = up[up[v][i-1]][i-1];
            for (size_t i=0; i<g[v].size(); ++i) {
                    int to = g[v][i];
                    if (to != p)
                            dfs (to, v);
            }
            tout[v] = ++timer;
    }
    bool upper (int a, int b) {
            return tin[a] <= tin[b] && tout[a] >= tout[b];
    }
    int lca (int a, int b) {
            if (upper (a, b))  return a;
            if (upper (b, a))  return b;
            for (int i=l; i>=0; --i)
                    if (! upper (up[a][i], b))
                            a = up[a][i];
            return up[a][0];
    }
    int main() {
            ... чтение n и g ...
            tin.resize (n),  tout.resize (n),  up.resize (n);
            l = 1;
            while ((1<<l) <= n)  ++l;
            for (int i=0; i<n; ++i)  up[i].resize (l+1);
            dfs (0);
            for (;;) {
                    int a, b; // текущий запрос
                    int res = lca (a, b); // ответ на запрос
            }
    }
}

C++ 解法

匹配/原始

int n, l;
vector < vector<int> > g;
vector<int> tin, tout;
int timer;
vector < vector<int> > up;
void dfs (int v, int p = 0) {
        tin[v] = ++timer;
        up[v][0] = p;
        for (int i=1; i<=l; ++i)
                up[v][i] = up[up[v][i-1]][i-1];
        for (size_t i=0; i<g[v].size(); ++i) {
                int to = g[v][i];
                if (to != p)
                        dfs (to, v);
        }
        tout[v] = ++timer;
}
bool upper (int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca (int a, int b) {
        if (upper (a, b))  return a;
        if (upper (b, a))  return b;
        for (int i=l; i>=0; --i)
                if (! upper (up[a][i], b))
                        a = up[a][i];
        return up[a][0];
}
int main() {
        ... чтение n и g ...
        tin.resize (n),  tout.resize (n),  up.resize (n);
        l = 1;
        while ((1<<l) <= n)  ++l;
        for (int i=0; i<n; ++i)  up[i].resize (l+1);
        dfs (0);
        for (;;) {
                int a, b; // текущий запрос
                int res = lca (a, b); // ответ на запрос
        }
}

Java 解法

自动草稿，提交前请检查

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int n, l;
    vector < ArrayList<Integer> > g;
    ArrayList<Integer> tin, tout;
    int timer;
    vector < ArrayList<Integer> > up;
    void dfs (int v, int p = 0) {
            tin[v] = ++timer;
            up[v][0] = p;
            for (int i=1; i<=l; ++i)
                    up[v][i] = up[up[v][i-1]][i-1];
            for (size_t i=0; i<g[v].size(); ++i) {
                    int to = g[v][i];
                    if (to != p)
                            dfs (to, v);
            }
            tout[v] = ++timer;
    }
    boolean upper (int a, int b) {
            return tin[a] <= tin[b] && tout[a] >= tout[b];
    }
    int lca (int a, int b) {
            if (upper (a, b))  return a;
            if (upper (b, a))  return b;
            for (int i=l; i>=0; --i)
                    if (! upper (up[a][i], b))
                            a = up[a][i];
            return up[a][0];
    }
    int main() {
            ... чтение n и g ...
            tin.resize (n),  tout.resize (n),  up.resize (n);
            l = 1;
            while ((1<<l) <= n)  ++l;
            for (int i=0; i<n; ++i)  up[i].resize (l+1);
            dfs (0);
            for (;;) {
                    int a, b; // текущий запрос
                    int res = lca (a, b); // ответ на запрос
            }
    }
}

Материал разбит как 算法ическая 题目: изучить постановку, понять асимптотику и реализовать 算法 на выбранном языке.

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。