E. Even Degree
找出欧拉图的欧拉回路,并将路径都存入数组中,计第一位l=1最后一位r=top(top为改欧拉图的边数)
找欧拉回路的操作:
从任意一点开始dfs,dfs的途中删除已经遍历过的边减小搜索规模,具体操作每次便利前向星的时候不让i直接等于e[i].next而是修改head[u]为e[i].next然后再让他等于head[u]
for(int i=head[u];i;i=head[u]){ head[u]=e[i].next; }
找出欧拉回路后先从l到r遍历如果碰到边的两端的度都为奇数,就从取当前最后一条边直到当前图只剩一条边的时候结束
void work(){ int l=1,r=top; while(l<r){ int id=st[l]; int u=E[id].u,v=E[id].v; if(deg[u]&1&°[v]&1){ id=st[r]; u=E[id].u,v=E[id].v; r--; } else l++; deg[u]--; deg[v]--; as.push_back(id); } }
全部代码如下:
#include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=5e5+10; inline int rd(){ int x; scanf("%d",&x); return x; } vector<int>as; int head[N],vis[N],cnt=1,top=0,st[N],deg[N]; struct edge{ int v,next,id; }e[N<<1]; struct EDGE{ int u,v; }E[N<<1]; inline void addedge(int u,int v,int id){ e[cnt]={v,head[u],id}; head[u]=cnt++; } void dfs(int u){ for(int i=head[u];i;i=head[u]){ int id=e[i].id,v=e[i].v; head[u]=e[i].next; if(vis[id])continue; vis[id]=1; dfs(v); st[++top]=id; } } void work(){ int l=1,r=top; while(l<r){ int id=st[l]; int u=E[id].u,v=E[id].v; if(deg[u]&1&°[v]&1){ id=st[r]; u=E[id].u,v=E[id].v; r--; } else l++; deg[u]--; deg[v]--; as.push_back(id); } } int main(){ int n=rd(),m=rd(); for(int i=1;i<=m;i++){ int u=rd(),v=rd(); E[i]=EDGE{u,v}; addedge(u,v,i); addedge(v,u,i); deg[u]++; deg[v]++; } int ans=m; for(int i=1;i<=n;i++){ top=0; dfs(1); if(top)work(),ans--; } printf("%d\n",ans); for(int i=0;i<as.size();i++){ printf("%d ",as[i]); } puts(""); }