Skip to content

graph tree

Jump to bottom
hotman edited this page Oct 25, 2020 · 1 revision

重心分解

#pragma once
#include<vector>
#include"graph_template.hpp"

/**
 * @brief 重心分解
 */

class centroid_decomposition{
    graph g;
    std::vector<int>used;
    std::vector<int>v;
    graph ch;
    int s;
    int dfs(int n,int p,int sz,int root){
        if(used[n])return 0;
        bool b=1;
        int res=1;
        for(auto e:g[n]){
            if(p==e)continue;
            auto t=dfs(e,n,sz,root);
            res+=t;
            if(t>sz/2)b=0;
        }
        if(!b||sz-res>sz/2)return res;
        if(root!=-1)ch[root].push_back(n);
        else s=n;
        v.push_back(n);
        used[n]=1;
        for(auto e:g[n]){
            dfs(e,n,dfs(e,n,g.size()*2,n),n);
        }
        return g.size()*2;
    }
    public:
    centroid_decomposition(const graph&g):g(g){
        int n=g.size();
        used.resize(n);
        ch.resize(n);
        dfs(0,-1,n,-1);
    }

    int get_root(){return s;}
    std::vector<int> operator[](int i){return ch[i];}
    std::vector<int> get_euler_tour(){return v;}
};

dinic

#pragma once
#include<vector>
#include<queue>
#include<cmath>
#include<limits>
#include<cassert>
#include<iostream>
#include<map>
#include<list>

/**
 * @brief 最大流(Dinic法)
 */

template<typename T>
struct dinic {
    struct edge {
        int to;
        typename std::list<edge>::iterator rev;
        T cap,flow;
        edge(int to,T cap):to(to),cap(cap),flow(T()){}
    };
    int n,src,dst;
    T ret=T();
    std::vector<std::list<edge>> g;
    std::vector<typename std::list<edge>::iterator>itr;
    std::vector<int>level,seen;
    std::map<std::pair<int,int>,bool>exist;
    std::map<std::pair<int,int>,typename std::list<edge>::iterator>m;
    dinic(int n,int s,int t):n(n),src(s),dst(t){g.assign(n,std::list<edge>());itr.resize(n);}

    void add_edge(int from, int to, T cap) {
        g[from].push_back(edge(to,cap));
        g[to].push_back(edge(from,0));
        m[std::make_pair(from,to)]=prev(g[from].end());
        m[std::make_pair(to,from)]=prev(g[to].end());
        g[from].back().rev=prev(g[to].end());
        g[to].back().rev=prev(g[from].end());
        exist[std::make_pair(from,to)]=1;
        exist[std::make_pair(to,from)]=1;
    }
    bool update_edge(int from, int to, T cap){
        if(cap>0){
            if(exist[std::make_pair(from,to)]){
                auto e=m[std::make_pair(from,to)];
                e->cap+=cap;
            }else{
                add_edge(from,to,cap);
            }
            return 1;
        }else{
            cap*=-1;
            if(exist[std::make_pair(from,to)]){
                auto e=m[std::make_pair(from,to)];
                if(e->cap-e->flow>=cap){
                    e->cap-=cap;
                }else{
                    e->cap-=cap;
                    T req=e->flow-e->cap;
                    e->flow-=req;
                    e->rev->flow+=req;
                    ret-=req;
                    assert(cancel(dst,to,req));
                    assert(cancel(from,src,req));
                    if(e->cap==0&&e->rev->cap==0){
                        g[from].erase(e);
                        g[to].erase(e->rev);
                        exist[std::make_pair(from,to)]=0;
                        exist[std::make_pair(to,from)]=0;
                    }
                }
                return 1;
            }else{
                return 0;
            }
        }
    }

    void bfs(int s) {
        level.assign(n,-1);
        std::queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for(edge e: g[v]){
                if (e.cap-e.flow > 0 and level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    T dfs(int v, int t,T f) {
        if (v == t) return f;
        for(auto &e=itr[v];e!=g[v].end();++e){
            if (e->cap-e->flow > 0 and level[v] < level[e->to]) {
                T d = dfs(e->to, t, std::min(f, e->cap-e->flow));
                if (d > 0) {
                    e->flow+=d;
                    e->rev->flow -= d;
                    return d;
                }
            }
        }
        return 0;
    }

    T __cancel(int v,int t,T f){
        if (v == t) return f;
        seen[v]=1;
        for (edge& e: g[v]){
            if (e.rev->flow > 0&&!seen[e.to]) {
                T d = __cancel(e.to, t, std::min(f,e.rev->flow));
                if (d > 0) {
                    e.flow+=d;
                    e.rev->flow-=d;
                    return d;
                }
            }
        }
        return 0;
    }
    T run() {
        T f;
        while (bfs(src), level[dst] >= 0) {
            for(int i=0;i<n;++i)itr[i]=g[i].begin();
            while ((f = dfs(src, dst, std::numeric_limits<T>::max())) > 0) {
                ret += f;
            }
        }
        return ret;
    }
    T cancel(int s,int t,T mx){
        T f;
        while(seen.assign(n,0),seen[s]=1,(f=__cancel(s, t, mx))>0)mx-=f;
        return mx==0;
    }
    T cap(int s,int t){
        if(exist[std::make_pair(s,t)]){
            return m[std::make_pair(s,t)]->cap;
        }else{
            return 0;
        }
    }
    T flow(int s,int t){
        if(exist[std::make_pair(s,t)]){
            return m[std::make_pair(s,t)]->flow;
        }else{
            return 0;
        }
    }
    void debug(){
        for(int i=0;i<n;++i)for(int j=0;j<n;++j){
            if(i==j)continue;
            if(flow(i,j)>0)std::cerr<<"("<<i<<","<<j<<")";
        }
        std::cerr<<'\n';
    }
};

push_relabel法O(V^2√E)

#pragma once
#include<vector>
#include<cmath>
#include<queue>
#include<tuple>

/**
 * @brief 最大流(push_relabel法O(V^2√E))
 */
template<typename T>
class push_relabel{
    int n;
    T f=0;
    using i64=long long;
    struct edge{
        int from,to,rev;
        T flow,cap;
    };
    std::vector<i64>h,d;
    std::vector<std::vector<edge*>>g;
    std::vector<size_t>seen;
    std::priority_queue<std::pair<i64,int>,std::vector<std::pair<i64,int>>,std::greater<std::pair<i64,int>>>que;
    public:
    push_relabel(int n):n(n){
        h.resize(n,0);
        d.resize(n,0);
        g.resize(n);
        seen.resize(n,0);
    }
    void add_edge(int u,int v,T cap){
        g[u].emplace_back(new edge{u,v,(int)g[v].size(),0,cap});
        g[v].emplace_back(new edge{v,u,(int)g[u].size()-1,0,0});
    }
    void push(edge* e){
        int u=e->from,v=e->to;
        i64 df=std::min(d[u],e->cap-e->flow);
        e->flow+=df;
        g[v][e->rev]->flow-=df;
        d[u]-=df;
        d[v]+=df;
        if(d[v]>0)que.emplace(h[v],v);
        if(d[u]>0)que.emplace(h[u],u);
    }
    void relabel(int u){
        i64 mn=n*2;
        for(edge* e:g[u]){
            if(e->cap-e->flow>0){
                mn=std::min(mn,h[e->to]);
            }
        }
        h[u]=1+mn;
        que.emplace(h[u],u);
    }
    void discharge(int u){
        while(d[u]>0){
            if(seen[u]<g[u].size()){
                edge* e=g[u][seen[u]];
                if(e->cap-e->flow>0 && h[u]==h[e->to]+1){
                    push(e);
                }else{
                    seen[u]+=1;
                }
            }else{
                relabel(u);
                seen[u]=0;
            }
        }
    }
    T run(int s,int t){
        h[s]=n;
        for(auto e:g[s]){
            d[s]+=e->cap;
            push(e);
        }
        while(!que.empty()){
            int u=que.top().second;
            que.pop();
            if(u==s||u==t)continue;
            discharge(u);
        }
        for(auto e:g[s])f+=e->flow;
        return f;
    }
};

最小費用流

#pragma once
#include<vector>
#include<queue>
#include<cmath>
#include"push_relabel.hpp"

/**
 * @brief 最小費用流(CostScaling)
 */

//Resは答えがlong longの最大値を超える時用
template<typename T,typename Res=T>
struct min_cost_flow{
    int v;
    Res ans=0;
    struct edge{
        int to;
        T cap,cost,st;
        int rev;
        bool is_rev,edge_rev;
        int id;
    };
    push_relabel<T> mf;
    std::vector<T>p;
    std::vector<vector<edge*>>e;//辺のキャパシティ
    std::vector<T>d;//頂点のキャパシティ
    std::queue<int>active;
    std::vector<tuple<int,int,T,T,T>>edges;
    T eps=1;
    int idx=0;
    std::vector<T>res;
    min_cost_flow(int v):v(v),mf(v+2),p(v,0),e(v),d(v,0){}
    void add_edge(int from,int to,T mn,T mx,T cost){
        edges.emplace_back(from,to,mn,mx,cost);
        res.push_back(0);
        if(from==to){
            if(cost<0)res[idx++]=mx,ans+=mx*cost;
            else res[idx++]=mn,ans+=mn*cost;
            return;
        }
        if(cost>=0){
            e[from].push_back(new edge{to,mx-mn,cost*v,mn,(int)e[to].size(),0,0,idx});
            e[to].push_back(new edge{from,0,-cost*v,mn,(int)e[from].size()-1,1,0,idx++});
            ans+=mn*cost;
            d[from]-=mn;d[to]+=mn;
            eps=max(eps,cost*v*v);
            mf.add_edge(from,to,mx-mn);
        }
        else{
            e[to].push_back(new edge{from,mx-mn,-cost*v,mx,(int)e[from].size(),0,1,idx});
            e[from].push_back(new edge{to,0,cost*v,mx,(int)e[to].size()-1,1,1,idx++});
            ans+=mx*cost;
            d[from]-=mx;d[to]+=mx;
            eps=max(eps,-cost*v*v);
            mf.add_edge(to,from,mx-mn);
        }
    }
    void add_edge(int from,int to,T cap,T cost){
        add_edge(from,to,T(),cap,cost);
    }

    Res flow(){
        for(;eps;eps>>=1){
            for(int i=0;i<v;i++){
                for(auto ed:e[i]){
                    if(ed->is_rev)continue;
                    if(ed->cost-p[i]+p[ed->to]<0){
                        T f=ed->cap;
                        ed->cap-=f;
                        d[i]-=f;
                        d[ed->to]+=f;
                        e[ed->to][ed->rev]->cap+=f;
                    }
                    if(ed->cost-p[i]+p[ed->to]>0){
                        T f=-e[ed->to][ed->rev]->cap;
                        ed->cap-=f;
                        d[i]-=f;
                        d[ed->to]+=f;
                        e[ed->to][ed->rev]->cap+=f;
                    }
                }
            }
            for(int i=0;i<v;i++)if(d[i]>0){active.emplace(i);}
            while(!active.empty()){
                int node=active.front();
                active.pop();
                if(d[node]<=0)continue;
                bool b=0;
                for(auto ed:e[node]){
                    if(!d[node])break;
                    if(-eps<=ed->cost-p[node]+p[ed->to]&&ed->cost-p[node]+p[ed->to]<0){
                        auto f=std::min(d[node],ed->cap);
                        if(!f)continue;
                        ed->cap-=f;
                        d[node]-=f;
                        d[ed->to]+=f;
                        e[ed->to][ed->rev]->cap+=f;
                        if(d[ed->to]>0)active.emplace(ed->to);
                        b=1;
                    }
                }
                if(d[node]>0)active.emplace(node);
                if(!b)p[node]+=eps;
            }
        }
        for(int i=0;i<v;i++)for(auto ed:e[i]){
            if(ed->is_rev)continue;
            ans+=e[ed->to][ed->rev]->cap*(ed->cost/v);
        }
        return ans;
    }
    bool ok(std::vector<T>b){
        T tmp=0,tmp2=0;
        for(int i=0;i<v;++i){
            if(d[i]+b[i]>=0){
                mf.add_edge(v,i,d[i]+b[i]);
                tmp2+=d[i]+b[i];
            }
            else{
                mf.add_edge(i,v+1,-(d[i]+b[i]));
                tmp+=-(d[i]+b[i]);
            }
        }
        return tmp==tmp2&&mf.run(v,v+1)==tmp;
    }
    Res run(int s,int t,T f){
        d[s]+=f;
        d[t]-=f;
        return flow();
    }
    Res run(std::vector<T>b){
        for(int i=0;i<v;++i)d[i]+=b[i];
        return flow();
    }
    std::vector<T> flow_result(){
        for(int i=0;i<v;i++)for(auto ed:e[i]){
            if(ed->is_rev)continue;
            res[ed->id]=ed->st+e[ed->to][ed->rev]->cap*(ed->edge_rev?-1:1);
        }
        return res;
    }
    //flow_resultを渡す
    std::vector<T>potential(const std::vector<T>& f){
        std::vector<T>p(v,0);
        std::vector<tuple<int,int,T>>g;
        int idx=0;
        for(auto [from,to,mn,mx,cost]:edges){
            if(mn<f[idx])g.emplace_back(to,from,-cost);
            if(f[idx]<mx)g.emplace_back(from,to,cost);
            idx++;
        }
        for(int i=0;i<v;++i)for(auto [s,t,c]:g){
            p[t]=std::min(p[t],p[s]+c);
        }
        return p;
    }
};

全方位木DP

#pragma once
#include<vector>

/**
 * @brief 全方位木DP
 */

template<typename T,typename F,typename Fix>
struct reroot{
    std::vector<std::vector<long long>>g;
    std::vector<int>p_list;
    std::vector<T>p_table;
    std::vector<bool>p_checked;
    std::vector<map<int,T>>table;
    std::vector<T>ans;
    F f;
    Fix fix;
    reroot(const std::vector<std::vector<long long>>& g,F f=F(),Fix fix=Fix()):g(g),f(f),fix(fix){
        int n=g.size();
        p_list.resize(n,-1);
        p_checked.resize(n,0);
        table.resize(n);
        p_table.resize(n,e);
        ans.resize(n,e);
        dfs1(0,-1);
        for(int i=0;i<n;++i)ans[i]=dfs2(i,-1);
    }
    T dfs1(int n,int p){
        p_list[n]=p;
        T tmp1=e,tmp2=e;
        std::vector<T>tmp(g[n].size());
        rep(i,g[n].size()){
            int t=g[n][i];
            if(t==p)continue;
            table[n][t]=tmp1;
            tmp1=f(tmp1,tmp[i]=dfs1(t,n));
        }
        for(int i=g[n].size()-1;i>=0;--i){
            int t=g[n][i];
            if(t==p)continue;
            table[n][t]=f(table[n][t],tmp2);
            tmp2=f(tmp[i],tmp2);
        }
        return fix(table[n][p]=tmp1,n,p);
    }
    T dfs2(int n,int p){
        if(n==-1)return e;
        if(!p_checked[n]){
            p_checked[n]=1;
            p_table[n]=dfs2(p_list[n],n);
        }
        if(p==-1){
            return f(table[n][p_list[n]],p_table[n]);
        }else{
            if(p_list[n]==-1)return fix(table[n][p],n,p);
            else return fix(f(table[n][p],p_table[n]),n,p);
        }
    }
    vector<T>query(){
        return ans;
    }
};

強連結成分分解

#pragma once
#include<vector>
#include<tuple>
#include<algorithm>
#include"graph_template.hpp"

/**
 * @brief 強連結成分分解
 */

std::pair<std::vector<int>,graph> scc(const graph& g){
    int n=g.size();
    std::vector<std::vector<int>>rev(n);
    for(int i=0;i<n;i++)for(auto e:g[i]){
        rev[e].emplace_back(i);
    }
    int idx=0;
    std::vector<int>v(n,-1);
    std::vector<bool>visited(n,0);
    auto dfs=[&](auto dfs,int now)->void{
        visited[now]=1;
        for(auto e:g[now]){
            if(!visited[e])dfs(dfs,e);
        }
        v[idx++]=now;
    };
    for(int i=0;i<n;i++){
        if(!visited[i])dfs(dfs,i);
    }
    idx=-1;
    std::vector<int>res(n,-1);
    auto rdfs=[&](auto rdfs,int now)->void{
        for(auto e:rev[now]){
            if(res[e]==-1)res[e]=idx,rdfs(rdfs,e);
        }
    };
    for(int i=n-1;i>=0;--i){
        if(res[v[i]]==-1){
            res[v[i]]=++idx;
            rdfs(rdfs,v[i]);
        }
    }
    idx++;
    std::vector<std::vector<int>>res2(idx);
    for(int i=0;i<n;i++)for(auto e:g[i]){
        if(res[i]==res[e])continue;
        res2[res[i]].push_back(res[e]);
    }
    for(int i=0;i<idx;i++){
        std::sort(res2[i].begin(),res2[i].end());
        res2[i].erase(std::unique(res2[i].begin(),res2[i].end()),res2[i].end());
    }
    return {res,res2};
}

2sat

#pragma once
#include<vector>
#include<algorithm>
#include"scc.hpp"
#include"graph_template.hpp"

/**
 * @brief 2-SAT
 */
struct two_sat{
    int n;
    graph v;
    std::vector<int>list;
    graph g;
    two_sat(int n):n(n){
        v.resize(n*2);
        list.resize(n*2,-1);
    }
    //add s==p&&t==q
    void add_edge(int s,int t,bool p,bool q){
        v[s+p*n].push_back(t+(1-q)*n);
        v[t+q*n].push_back(s+(1-p)*n);
    }
    bool solve(){
        static int scced=0;
        static bool ans=1;
        if(!scced){
            scced=1;
            tie(list,v)=scc(v);
            for(int i=0;i<n;i++){
                if(list[i]==list[i+n])ans=0;
            }
        }
        return ans;
    }
    bool operator[](int i){
        return list[i]>list[i+n];
    }
};

二辺連結成分分解

#include<vector>
#include<stack>
#include<algorithm>
#include"graph_template.hpp"

/**
 * @brief 二辺連結成分分解
 */

struct two_edge_connectivity{
	std::vector<int>order,cmp;
	std::stack<int> s,roots;
	std::vector<bool> ins;
	std::vector<std::vector<int>>each_bcc;
	std::vector<std::pair<int,int>>brige;
	two_edge_connectivity(graph g){
		int n=g.size();
		order.resize(n,0);
		ins.resize(n,0);
		cmp.resize(n);
		for(int i=0;i<n;i++){
			if(!order[i])dfs(g,i,-1);
		}
	}
	void dfs(const graph& g,int v,int p){
		order[v]=(p==-1?0:order[p])+1;
		s.emplace(v);
		ins[v]=1;
		roots.emplace(v);
		bool f=1;
		for(auto e:g[v]){
			if(e==p&&f){f=0;continue;}
			if(!order[e])dfs(g,e,v);
			else if(e!=v&&ins[e])while(order[roots.top()]>order[e])roots.pop();
		}
		if(v==roots.top()){
			if(p!=-1)brige.push_back(std::minmax(p,v));
			std::vector<int>bcc;
			while(1){
				int e=s.top();s.pop();ins[e]=0;
				bcc.push_back(e);
				cmp[v]=each_bcc.size();
				if(e==v)break;
			}
			each_bcc.push_back(bcc);
			roots.pop();
		}
	}
	auto get_bcc(){return each_bcc;}
	auto get_v(){return cmp;}
	auto get_brige(){return brige;}
};
# トポソ
```cpp
#pragma once
#include<vector>
#include<algorithm>

/**
 * @brief トポロジカルソート
 */

std::vector<int>tsort(std::vector<std::vector<int>>G){
	std::vector<int> visited(G.size(),0);
	std::vector<int> start(G.size(),1);
	for(int i=0;i<(int)G.size();i++)for(int j=0;j<(int)G[i].size();j++){
		start[G[i][j]]=0;
	}
	std::vector<int>res(G.size());
    int idx=0;
	auto f=[&](auto f,int v)->void{
		if(visited[v])return;
		for(auto t:G[v])f(f,t);
		res[idx++]=v;
		visited[v]=1;
	};
	for(int i=0;i<(int)G.size();i++)if(start[i])f(f,i);
	std::reverse(res.begin(),res.end());
	return res;
}

最大独立集合

#pragma once
#include<tuple>
#include<vector>
#include<bitset>
#include"graph_template.hpp"

/**
 * @brief 最大独立集合(V<=50)
 */

std::pair<int,std::bitset<50>> __maximum_independent_set(std::vector<std::bitset<50>>v,std::bitset<50>b=std::bitset<50>()){
	int n=v.size();
	auto del=[&](int k){
		for(int i=0;i<n;++i){
			v[k][i]=0;
			v[i][k]=0;
		}
		b[k]=1;
	};
	int t=-1;
	for(int i=0;i<n;++i)if(b[i]==0)t=i;
	if(t==-1)return std::make_pair(0,std::bitset<50>());
	if(v[t].count()<=1){
		for(int i=0;i<n;++i)if(v[t][i])del(i);
		del(t);
		auto p=__maximum_independent_set(v,b);
		p.first++;
		p.second[t]=1;
		return p;
	}else{
		std::vector<int>tmp;
		for(int i=0;i<n;++i)if(v[t][i])tmp.push_back(i);
		del(t);
		auto p=__maximum_independent_set(v,b);
		for(auto e:tmp)del(e);
		auto q=__maximum_independent_set(v,b);
		q.first++;
		q.second[t]=1;
		return p.first>q.first?p:q;
	}
}

std::vector<int> maximum_independent_set(const graph& g){
	std::vector<std::bitset<50>>v(g.size());
	for(size_t i=0;i<g.size();++i){
		for(auto e:g[i]){
			v[i][e]=1;
		}
	}
	auto res=__maximum_independent_set(v);
	std::vector<int>ret;
	for(size_t i=0;i<res.second.size();++i){
		if(res.second[i])ret.push_back(i);
	}
	return ret;
}

LCA

#pragma once
#include<vector>
#include"graph_template.hpp"

/**
 * @brief LCA(HL分解)&amp;lt;O(N),O(logN)&amp;gt;
 */

struct lca{
    graph g;
    std::vector<int>sz,in,out,nxt,par;
    lca(const graph& g,int s):g(g){
        int n=g.size();
        sz.resize(n,0);
        in.resize(n,0);
        out.resize(n,0);
        nxt.resize(n,s);
        par.resize(n,s);
        dfs_sz(s,-1);
        dfs_hld(s,-1);
    }
    void dfs_sz(int v,int p) {
        sz[v] = 1;
        for(auto &u: g[v]) {
            if(p==u)continue;
            dfs_sz(u,v);
            sz[v]+=sz[u];
            if(sz[u]>sz[g[v][0]])std::swap(u,g[v][0]);
        }
    }
    void dfs_hld(int v,int p) {
        static int t=0;
        in[v]=t++;
        for(auto u: g[v]){
            if(p==u)continue;
            nxt[u]=(u==g[v][0]?nxt[v]:u);
            par[u]=(u==g[v][0]?par[v]:v);
            dfs_hld(u,v);
        }
        out[v] = t;
    }
    int query(int s,int t){
        while(nxt[s]!=nxt[t]){
			if(sz[nxt[s]]>sz[nxt[t]])t=par[t];
			else s=par[s];
		}
        return sz[s]>sz[t]?s:t;
    }
    int distance(int s,int t){
		int res=0;
		while(nxt[s]!=nxt[t]){
			if(sz[nxt[s]]>sz[nxt[t]]){
				res+=in[t]-in[nxt[t]]+1;
				t=par[t];
			}
			else {
				res+=in[s]-in[nxt[s]]+1;
				s=par[s];
			}
		}
		return res+std::abs(in[s]-in[t]);
	}
};
Clone this wiki locally