Cf1494f delete the edges (Euler circuit)

Preface

Go far go far …
I've been thinking about how to flip the parity of a chain , But I didn't realize that it must be a chrysanthemum in the end .

analysis

One state is to take an Euler loop , Legitimacy is easier to portray , So consider thinking in reverse , How to delete some edges with the walking method of state two , Make the remaining graph exist Euler path .

So what is the walking method of state two ？
Because the edge must be deleted at last , Perceptual understanding , The picture of state 2 going out must be a chrysanthemum .

So just discuss each point directly as the chrysanthemum Center . Because the rest of the diagram may not be connected , It also needs to be legal to run Euler road violently .

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("ok\n")
inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}


const int N=6050;
const int mod=998244353;
ll n,m,k;
inline ll ksm(ll x,ll k,int mod){
    
  ll res(1);
  while(k){
    
    if(k&1) res=x*res%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

struct node{
    
  int to,nxt,id;
}p[N<<1];
int fi[N],cur[N],ecnt;
inline void addline(int x,int y,int id){
    
  p[++ecnt]=(node){
    y,fi[x],id};fi[x]=ecnt;
  return;
}
int zhan[N],top;
int du[N];
bool vis[N];
void dfs(int x){
    
  //debug("x=%d\n",x);
  for(int i=cur[x];~i;i=cur[x]){
    
    cur[x]=p[i].nxt;
    if(vis[p[i].id]) continue;
    vis[p[i].id]=1;
    dfs(p[i].to);
  }
  zhan[++top]=x;
}
void init(){
    
  for(int i=1;i<=n;i++) cur[i]=fi[i];
  memset(vis,0,sizeof(vis));
  top=0;
}

int cnt,rt;
inline void calc(int x,int ban,int e){
    
  init();
  --e;
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    if(!(du[to]&1)) continue;
    if(to==ban) continue;
    vis[p[i].id]=1;    
  }
  dfs(x);
  if(top-1+e==m){
    
    printf("%d\n",top+1+2*e);
    for(int i=1;i<=top;i++) printf("%d ",zhan[i]);
    printf("-1 ");
    for(int i=fi[x];~i;i=p[i].nxt){
    
      int to=p[i].to;
      if(to==ban) continue;
      if(du[to]&1) printf("%d %d ",to,x);
    }
    exit(0);
  }
}
inline void work(int x){
    
  int num=du[x]&1,e(0);
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    num+=(du[to]&1);
    e+=(du[to]&1);
  }
  if(num==cnt){
    
    for(int i=fi[x];~i;i=p[i].nxt){
    
      int to=p[i].to;
      if(du[to]&1) calc(x,to,e);
    }
  }
  if(num>=cnt-1){
    
    init();
    //ok;
    for(int i=fi[x];~i;i=p[i].nxt){
    
      int to=p[i].to;
      if(du[to]&1) vis[p[i].id]=1;
    }
    dfs(x);
    if(top-1+e==m){
    
      //printf("top=%d e=%d\n",top,e);
      printf("%d\n",top+1+2*e);
      for(int i=1;i<=top;i++) printf("%d ",zhan[i]);
      printf("-1 ");
      for(int i=fi[x];~i;i=p[i].nxt){
    
	int to=p[i].to;
	if(du[to]&1) printf("%d %d ",to,x);
      }
      exit(0);
    }
  }
  
  return;
}

signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  memset(fi,-1,sizeof(fi));ecnt=-1;
  cnt=-1;
  n=read();m=read();
  for(int i=1;i<=m;i++){
    
    int x=read(),y=read();
    addline(x,y,i);
    addline(y,x,i);
    du[x]++;
    du[y]++;
  }
  cnt=0,rt=1;
  for(int i=1;i<=n;i++){
    
    if(du[i]&1){
    
      ++cnt;
      rt=i;
    }
  }
  if(cnt<=2){
    
    init();
    dfs(rt);
    printf("%d\n",top);
    while(top) printf("%d ",zhan[top--]);
    return 0;
  }
  for(int i=1;i<=n;i++) work(i);
  puts("0");
  return 0;
}
/* */