【模板】【好题】欧拉回路+建图——cf1361C

这题很奇怪啊，思路没问题但是自己写的有问题

碰到大数据总是T，也不知道错在哪里（也许是爆栈了？）

ps:原来是在求欧拉回路时边指针没有向前推

从小到大枚举答案k
那么所有连接的边至少是2^k的倍数
这种模型可以想到欧拉回路；
图上2^k个点，对应权值是[0..2^k-1]，每个大珠子看成一条边，u,v就是小珠子%2^k后的值
图建起来后判一下是否是欧拉回路就行

这题的可以用作稀疏图的欧拉回路模板

int to[N],nxt[N],h[N],tot,ve[N],stk[N],top;
inline void add(int x,int y){nxt[++tot]=h[x];to[tot]=y;ve[tot]=0;h[x]=tot;}
void init(){tot=1;memset(h,0,sizeof h);}

void euler(int u){
    for(int &i=h[u];i;i=nxt[i]){// i作为点u边集的指针，不停往前推进，保证一条边不会被多次遍历到 
        if(ve[i])continue;
        ve[i]=ve[i^1]=1;
        int e=i^1; //这里要记录一下边的编号，因为后面指针i会往前推 
        euler(to[i]);
        stk[++top]=(e);
    }
}

完整代码

#include<bits/stdc++.h>
using namespace std;
#define N 1500005

int n,a[N],b[N];


int to[N],nxt[N],h[N],tot,ve[N],vv[N],d[N],ans,stk[N],top;
inline void add(int x,int y){nxt[++tot]=h[x];to[tot]=y;ve[tot]=0;h[x]=tot;}
void dfs(int u){
    vv[u]=1;
    for(int i=h[u];i;i=nxt[i])if(!vv[to[i]])dfs(to[i]);
}
void euler(int u){
    for(int &i=h[u];i;i=nxt[i]){// i作为点u边集的指针，不停往前推进，保证一条边不会被多次遍历到 
        if(ve[i])continue;
        ve[i]=ve[i^1]=1;
        int e=i^1; //这里要记录一下边的编号，因为后面指针i会往前推 
        euler(to[i]);
        stk[++top]=(e);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    int ans=-1;
    for(int k=0;k<=20;k++){
        tot=1;memset(h,0,sizeof h);
        for(int i=0;i<(1<<k);i++)d[i]=vv[i]=0;
        
        int mask=(1<<k)-1;
        for(int i=1;i<=n;i++){
            int u=a[i]&mask,v=b[i]&mask;
            add(u,v);add(v,u);
            d[u]++;d[v]++;
        } 
        int f=0;
        for(int i=0;i<=mask;i++)if(d[i]%2)f=1;
        if(!f){
            for(int i=0;i<=mask;i++)if(d[i]){dfs(i);break;}
            for(int i=0;i<=mask;i++)if(d[i] && !vv[i]){f=1;break;}
        }
        if(f){
            ans=k-1;break;
        }
        top=0;
        for(int i=0;i<=mask;i++)if(d[i]){euler(i);break;}
    }
    if(ans==-1)ans=20;
    cout<<ans<<'
';
    for(int i=1;i<=top;i++)printf("%d %d ",stk[i]-1,(stk[i]^1)-1);
}