其实这个想法早就有了,奈何应用实在不多.
这个存图方法可以以较小的常数(自以为吧),达到约等于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; } /* 麻术行走的日复一日 忘却了曾仰望的星辰~ */
标签:int,void,存图,buc,ifo,方法,奇怪,reserve From: https://www.cnblogs.com/QedDust/p/17830029.html