cplib/graph/lca.hpp

• View this file on GitHub
• Last update: 2022-01-02 13:06:06-05:00
• Include: #include "cplib/graph/lca.hpp"

Depends on

• cplib/graph/graph.hpp

Required by

• cplib/graph/pathqueries.hpp

Code

#ifndef CPLIB_LCA_HPP
#define CPLIB_LCA_HPP

#include "cplib/graph/graph.hpp"
#include <cmath>
#include <functional>
#include <vector>

namespace cplib
{
using namespace std;

template <typename W>
struct LCA
{
    Graph<W> const &    g;
    vector<vector<int>> up;
    vector<int>         tin, tout;

    LCA(Graph<W> const &g)
        : g(g), up(g.size(), vector<int>(log2(g.size()) + 2)), tin(g.size()),
          tout(g.size())
    {
        int                      timer = 0, n = g.size();
        function<void(int, int)> dfs = [&](int u, int p)
        {
            tin[u]   = ++timer;
            up[u][0] = p;
            for (int i = 1, height = up[0].size(); i < height; ++i)
                up[u][i] = up[up[u][i - 1]][i - 1];

            for (auto vw : g[u])
                if (g.vertex(vw) != p)
                    dfs(g.vertex(vw), u);

            tout[u] = ++timer;
        };

        for (int u = 0; u < n; ++u)
            if (tin[u] == 0)
                dfs(u, u);
    }

    bool is_ancestor(int u, int v) const
    {
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }

    int ancestor(int u, int k) const
    {
        int i;
        while (k)
        {
            i = 8 * sizeof(k) - __builtin_clz(k) - 1;
            u = up[u][i];
            k ^= 1LL << i;
        }
        if (up[u][0] == u)
            return -1;
        return u;
    }

    int lca(int u, int v) const
    {
        if (is_ancestor(u, v))
            return u;
        if (is_ancestor(v, u))
            return v;
        for (int i = up[0].size() - 1; i >= 0; --i)
            if (!is_ancestor(up[u][i], v))
                u = up[u][i];
        return up[u][0];
    }

    int operator()(int u, int v) const { return lca(u, v); }
};
} // namespace cplib

#endif // CPLIB_LCA_HPP

#line 1 "cplib/graph/lca.hpp"



#line 1 "cplib/graph/graph.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace cplib
{
using namespace std;

template <typename W>
struct Graph
{
    using adj_list = vector<pair<int, W>>;
    vector<adj_list> g;

    Graph(int n = 0) : g(n) {}

    size_t size() const { return g.size(); }
    int    vertex(pair<int, W> e) const { return e.first; }
    void   add_edge(int u, int v) { g[u].emplace_back(v, W()); }
    void   add_edge(int u, int v, W weights) { g[u].emplace_back(v, weights); }
    void   add_undirected_edge(int u, int v)
    {
        g[u].emplace_back(v, W());
        g[v].emplace_back(u, W());
    }
    void add_undirected_edge(int u, int v, W weights)
    {
        g[u].emplace_back(v, weights);
        g[v].emplace_back(u, weights);
    }
    int add_node(void)
    {
        g.push_back({});
        return g.size() - 1;
    }

    adj_list &operator[](int u) { return g[u]; }
    adj_list  operator[](int u) const { return g[u]; }

    typename vector<adj_list>::iterator begin() { return g.begin(); };
    typename vector<adj_list>::iterator end() { return g.end(); }

    typename vector<adj_list>::const_iterator begin() const
    {
        return g.begin();
    };
    typename vector<adj_list>::const_iterator end() const { return g.end(); }
};

template <>
struct Graph<void>
{
    using adj_list = vector<int>;
    vector<adj_list> g;

    Graph(int n = 0) : g(n) {}

    size_t size() const { return g.size(); }
    int    vertex(int e) const { return e; }
    void   add_edge(int u, int v) { g[u].emplace_back(v); }
    void   add_undirected_edge(int u, int v)
    {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int add_node(void)
    {
        g.push_back({});
        return g.size() - 1;
    }

    adj_list &operator[](int u) { return g[u]; }
    adj_list  operator[](int u) const { return g[u]; }

    typename vector<adj_list>::iterator begin() { return g.begin(); };
    typename vector<adj_list>::iterator end() { return g.end(); }

    typename vector<adj_list>::const_iterator begin() const
    {
        return g.begin();
    };
    typename vector<adj_list>::const_iterator end() const { return g.end(); }
};

using UndirectedGraph = Graph<void>;

} // namespace cplib


#line 5 "cplib/graph/lca.hpp"
#include <cmath>
#include <functional>
#line 8 "cplib/graph/lca.hpp"

namespace cplib
{
using namespace std;

template <typename W>
struct LCA
{
    Graph<W> const &    g;
    vector<vector<int>> up;
    vector<int>         tin, tout;

    LCA(Graph<W> const &g)
        : g(g), up(g.size(), vector<int>(log2(g.size()) + 2)), tin(g.size()),
          tout(g.size())
    {
        int                      timer = 0, n = g.size();
        function<void(int, int)> dfs = [&](int u, int p)
        {
            tin[u]   = ++timer;
            up[u][0] = p;
            for (int i = 1, height = up[0].size(); i < height; ++i)
                up[u][i] = up[up[u][i - 1]][i - 1];

            for (auto vw : g[u])
                if (g.vertex(vw) != p)
                    dfs(g.vertex(vw), u);

            tout[u] = ++timer;
        };

        for (int u = 0; u < n; ++u)
            if (tin[u] == 0)
                dfs(u, u);
    }

    bool is_ancestor(int u, int v) const
    {
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }

    int ancestor(int u, int k) const
    {
        int i;
        while (k)
        {
            i = 8 * sizeof(k) - __builtin_clz(k) - 1;
            u = up[u][i];
            k ^= 1LL << i;
        }
        if (up[u][0] == u)
            return -1;
        return u;
    }

    int lca(int u, int v) const
    {
        if (is_ancestor(u, v))
            return u;
        if (is_ancestor(v, u))
            return v;
        for (int i = up[0].size() - 1; i >= 0; --i)
            if (!is_ancestor(up[u][i], v))
                u = up[u][i];
        return up[u][0];
    }

    int operator()(int u, int v) const { return lca(u, v); }
};
} // namespace cplib

Back to top page