奇怪的存图方法

其实这个想法早就有了,奈何应用实在不多.
这个存图方法可以以较小的常数(自以为吧),达到约等于vector存图的访问连续性.
使用了一些计数排序的思想.

namespace graph{
using e_ifo=int;
int _buc[maxn],*buc=_buc+1;//if 0 index
std::vector<std::pair<int,e_ifo> > H;
e_ifo E[maxm];
struct nod{
    int x,y;
    e_ifo*begin(){return E+x;}
    e_ifo*end(){return E+y;}
}G[maxn];
void reserve(int m){
    H.reserve(m);   
}
void adde(int u,auto&&v){
    ++buc[u],H.emplace_back(u,v);
}
void build(){
    for(int i=1;i<maxn;++i){buc[i]+=buc[i-1];}
    for(auto&[u,v]:H){G[u]={buc[u-1],buc[u]};}
    for(auto&[u,v]:H){E[--buc[u]]=std::move(v);}
    H.clear();
}
}
using graph::adde;
using graph::G;

使用的时候先reserve一下要存的边的数量.

然后调用adde.

最后build.

然后类似vector存图那样用就行了.

例:用这个存图方式写三元环计数.

#include<bits/stdc++.h>
using i64=long long;
constexpr int maxn=1e5+5,maxm=2e5+5;
namespace graph{
using e_ifo=int;
int _buc[maxn],*buc=_buc+1;//if 0 index
std::vector<std::pair<int,e_ifo> > H;
e_ifo E[maxm];
struct nod{
    int x,y;
    e_ifo*begin(){return E+x;}
    e_ifo*end(){return E+y;}
}G[maxn];
void reserve(int m){
    H.reserve(m);   
}
void adde(int u,auto&&v){
    ++buc[u],H.emplace_back(u,v);
}
void build(){
    for(int i=1;i<maxn;++i){buc[i]+=buc[i-1];}
    for(auto&[u,v]:H){G[u]={buc[u-1],buc[u]};}
    for(auto&[u,v]:H){E[--buc[u]]=std::move(v);}
    H.clear();
}
}
using graph::adde;
using graph::G;
template<class T>using vec=std::vector<T>;
using std::cin;
using std::cout;
void solve(){
    int n,m;
    cin>>n>>m;
    graph::reserve(m);
    vec<std::pair<int,int> > alle(m);
    vec<int> deg(n+1),tim(n+1);
    for(auto&[u,v]:alle){
        cin>>u>>v,++deg[u],++deg[v];
    }
    for(auto [u,v]:alle){
        if((deg[u]<deg[v])||(deg[u]==deg[v]&&u<v)){std::swap(u,v);}
        adde(v,u);
    }
    graph::build();
    int ans=0;
    for(int u=1;u<=n;++u){
        for(auto to:G[u]){
            tim[to]=u;
        }
        for(auto to:G[u]){
            for(auto tt:G[to]){
                if(tim[tt]==u){
                    ++ans;
                }
            }
        }
    }
    cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}
/*
麻术行走的日复一日
忘却了曾仰望的星辰~
*/