Метод двоичного подъёма: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
struct Graph {
    vector<vector<int>> graph, ancestor;
    vector<int> l, r, depth;
    int timer = 0;
    Graph(int vertexCount) :
        graph(vertexCount),
        ancestor(vertexCount, vector<int>(20)),
        l(vertexCount),
        r(vertexCount),
        depth(vertexCount) {}
    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    void dfs(int v, int parent) {
        depth[v] = (v == parent ? 0 : depth[parent] + 1);
        l[v] = timer++;
        ancestor[v][0] = parent;
        for (int i = 1; i < ancestor[v].size(); i++)
            ancestor[v][i] = ancestor[ancestor[v][i - 1]][i - 1];
        for (int to : graph[v])
            if (to != parent)
                dfs(to, v);
        r[v] = timer++;
    }
    void prepare(int root) {
        dfs(root, root);
    }
    bool isAncestor(int a, int b) {
        return l[a] <= l[b] && r[b] <= r[a];
    }
    int lca(int a, int b) {
        if (isAncestor(a, b))
            return a;
        if (isAncestor(b, a))
            return b;
        for (int i = ancestor[a].size() - 1; i >= 0; i--)
            if (!isAncestor(ancestor[a][i], b))
                a = ancestor[a][i];
        return ancestor[a][0];
    }
    int distance(int a, int b) {
        int l = lca(a, b);
        int da = depth[a] - depth[l];
        int db = depth[b] - depth[l];
        return da + db;
    }
};
== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru &mdash; Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]
* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru &mdash; Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki &mdash; Метод двоичного подъёма]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki &mdash; Метод двоичного подъёма]
* [http://github.com/indy256/codelibrary/blob/master/java/src/LcaSparseTable.java CodeLibrary &mdash; LCA: Sparse Table] (несмотря на название, приведён код метода двоичного подъёма)  
* [https://algorithmica.org/ru/lca algorithmica.org — Корневые деревья]
* [http://github.com/ADJA/algos/blob/master/Graphs/LCABinary.cpp Algos &mdash; Finding LCA (Least common ancestor) of two vertices in the tree]
* [https://usaco.guide/gold/tree-euler usaco.guide — Euler Tour Technique]
* [https://usaco.guide/plat/binary-jump usaco.guide — Binary Jumping]
* [https://github.com/indy256/codelibrary/blob/master/java/graphs/lca/LcaSparseTable.java indy256/codelibrary/java/graphs/lca/LcaSparseTable.java] (несмотря на название, приведён код метода двоичного подъёма)  
* [http://github.com/ADJA/algos/blob/master/Graphs/LCABinary.cpp ADJA/algos/Graphs/LCABinary.cpp]


[[Category:Наименьший общий предок]]
[[Category:Наименьший общий предок]]

Текущая версия от 18:29, 27 июня 2023

struct Graph {
    vector<vector<int>> graph, ancestor;
    vector<int> l, r, depth;
    int timer = 0;

    Graph(int vertexCount) :
        graph(vertexCount),
        ancestor(vertexCount, vector<int>(20)),
        l(vertexCount),
        r(vertexCount),
        depth(vertexCount) {}

    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    void dfs(int v, int parent) {
        depth[v] = (v == parent ? 0 : depth[parent] + 1);
        l[v] = timer++;

        ancestor[v][0] = parent;
        for (int i = 1; i < ancestor[v].size(); i++)
            ancestor[v][i] = ancestor[ancestor[v][i - 1]][i - 1];

        for (int to : graph[v])
            if (to != parent)
                dfs(to, v);

        r[v] = timer++;
    }

    void prepare(int root) {
        dfs(root, root);
    }

    bool isAncestor(int a, int b) {
        return l[a] <= l[b] && r[b] <= r[a];
    }

    int lca(int a, int b) {
        if (isAncestor(a, b))
            return a;
        if (isAncestor(b, a))
            return b;

        for (int i = ancestor[a].size() - 1; i >= 0; i--)
            if (!isAncestor(ancestor[a][i], b))
                a = ancestor[a][i];

        return ancestor[a][0];
    }

    int distance(int a, int b) {
        int l = lca(a, b);
        int da = depth[a] - depth[l];
        int db = depth[b] - depth[l];
        return da + db;
    }
};

Ссылки