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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
(Отмена правки 2694, сделанной Ctrlalt (обсуждение))
Метка: отмена
Строка 59: Строка 59:
     }
     }
  };
  };
== Ссылки ==
* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за 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 — Метод двоичного подъёма]
* [https://algorithmica.org/ru/lca algorithmica.org — Корневые деревья]
* [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:Наименьший общий предок]]

Версия от 08:23, 31 июля 2021

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 (!l[to])
                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;
    }
};

Ссылки