Graph2/DoublingLowestCommonAncestor.hpp

• View this file on GitHub
• Last update: 2023-07-17 18:02:31+09:00
• Include: #include "Graph2/DoublingLowestCommonAncestor.hpp"

Depends on

• Graph2/GraphTemplate.hpp

Code

#include "./GraphTemplate.hpp"

template< typename T >
struct DoublingLowestCommonAncestor{
    const Graph<T> &g;
    vector<int> dep;
    int LOG;
    //table[i][j]は点jの2^i個上の親情報
    vector<vector<int>> table;

    DoublingLowestCommonAncestor(const Graph< T > &g_) : g(g_), dep(g_.V),LOG(32 - __builtin_clz(g_.V))
    {
        table.assign(LOG, vector<int>(g_.V, -1));
    }
 
    void dfs(int idx, int par, int d)
    {
        //1個上の親の記録
        table[0][idx] = par;
        dep[idx] = d;
        for(auto &to : g[idx])
        {
            if(to!=par) dfs(to, idx, d+1);
        }
    }
 
    //根としたい点をroot
    void build(int root){
        dfs(root, -1, 0);
        for(int k = 0; k + 1 < LOG; k++)
        {
            for(int i = 0; i < (int)table[k].size(); i++)
            {
                if(table[k][i]==-1) table[k + 1][i] = -1;
                else                table[k + 1][i] = table[k][table[k][i]];
            }
        }
    }
 
    //u,vのlcaを求める
    int query(int u, int v)
    {
        //dep[u]>dep[v]として進める
        if(dep[u] > dep[v]) swap(u,v);
        //深さをそろえる
        for(int i = LOG - 1; i >= 0; i--)
        {
            if(((dep[v]-dep[u])>>i)&1) v=table[i][v];
        }
        if(u==v) return u;
        for(int i=LOG-1;i>=0;i--){
            if(table[i][u]!=table[i][v]){
                u=table[i][u];
                v=table[i][v];
            }
        }
        return table[0][u];
    }
    
    // 呼び出すたびO(logn)
    int dis(int u,int v){
        int p=query(u,v);
        return dep[u]+dep[v]-2*dep[p];
    }
 
    // 深さを返す
    int operator[](const int &k) const{
        return dep[k];
    }
 
    //頂点xのk個上の親を求める。無ければ-1
    int parent(int x,int k){
        int ret=x;
        for(int i=LOG-1;i>=0 and ret>=0;i--){
            if((k>>i)&1) ret=table[i][ret];
        }
        return ret;
    }
};

#line 1 "Graph2/GraphTemplate.hpp"



// graph template
// ref : https://ei1333.github.io/library/graph/graph-template.hpp
template<typename T=int>
struct Edge{
    int from,to;
    T w;
    int idx;
    Edge()=default;
    Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}
    operator int() const{return to;}
};

template<typename T=int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int V,E;
    Graph()=default;
    Graph(int n):g(n),V(n),E(0){}

    int size(){
        return (int)g.size();
    }
    void resize(int k){
        g.resize(k);
        V=k;
    }
    inline const vector<Edge<T>> &operator[](int k)const{
        return (g.at(k));
    }
    inline vector<Edge<T>> &operator[](int k){
        return (g.at(k));
    }
    void add_directed_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E++);
    }
    void add_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E);
        g[to].emplace_back(to,from,cost,E++);
    }
    void read(int m,int pad=-1,bool weighted=false,bool directed=false){
        for(int i=0;i<m;i++){
            int u,v;cin>>u>>v;
            u+=pad,v+=pad;
            T w=T(1);
            if(weighted) cin>>w;
            if(directed) add_directed_edge(u,v,w);
            else         add_edge(u,v,w);
        }
    }
};


#line 2 "Graph2/DoublingLowestCommonAncestor.hpp"

template< typename T >
struct DoublingLowestCommonAncestor{
    const Graph<T> &g;
    vector<int> dep;
    int LOG;
    //table[i][j]は点jの2^i個上の親情報
    vector<vector<int>> table;

    DoublingLowestCommonAncestor(const Graph< T > &g_) : g(g_), dep(g_.V),LOG(32 - __builtin_clz(g_.V))
    {
        table.assign(LOG, vector<int>(g_.V, -1));
    }
 
    void dfs(int idx, int par, int d)
    {
        //1個上の親の記録
        table[0][idx] = par;
        dep[idx] = d;
        for(auto &to : g[idx])
        {
            if(to!=par) dfs(to, idx, d+1);
        }
    }
 
    //根としたい点をroot
    void build(int root){
        dfs(root, -1, 0);
        for(int k = 0; k + 1 < LOG; k++)
        {
            for(int i = 0; i < (int)table[k].size(); i++)
            {
                if(table[k][i]==-1) table[k + 1][i] = -1;
                else                table[k + 1][i] = table[k][table[k][i]];
            }
        }
    }
 
    //u,vのlcaを求める
    int query(int u, int v)
    {
        //dep[u]>dep[v]として進める
        if(dep[u] > dep[v]) swap(u,v);
        //深さをそろえる
        for(int i = LOG - 1; i >= 0; i--)
        {
            if(((dep[v]-dep[u])>>i)&1) v=table[i][v];
        }
        if(u==v) return u;
        for(int i=LOG-1;i>=0;i--){
            if(table[i][u]!=table[i][v]){
                u=table[i][u];
                v=table[i][v];
            }
        }
        return table[0][u];
    }
    
    // 呼び出すたびO(logn)
    int dis(int u,int v){
        int p=query(u,v);
        return dep[u]+dep[v]-2*dep[p];
    }
 
    // 深さを返す
    int operator[](const int &k) const{
        return dep[k];
    }
 
    //頂点xのk個上の親を求める。無ければ-1
    int parent(int x,int k){
        int ret=x;
        for(int i=LOG-1;i>=0 and ret>=0;i--){
            if((k>>i)&1) ret=table[i][ret];
        }
        return ret;
    }
};

Back to top page