acm-(欧拉回路、思维、好题)2020 ECNU Campus Online Invitational Contest E. Even Degree

cf传送门
vj传送门
容易发现跟欧拉回路有关联，考虑先求出每个连通块的欧拉回路，并记录在队列中，然后考虑将队首的边依次放入答案序列中，并与此同时记录每个点的度数变化，如果当前边的两个端点的度数都是奇数，那么从队尾取边，直到队列中只有一条边的时候，就停止，然后考虑下一个连通块的删边顺序。

欧拉回路如何求解呢？考虑从任意一个点开始dfs，遍历过的边都删除掉(用前向星)，删除的方式就是改变$h[u]$的值即可，注意同一个点在dfs的过程中可能会多次访问，因此如果不删边会导致复杂度爆炸。

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

const int maxn = 5e5+5;
const int MAX = 1e9;
const int inf = 2147483647;
typedef long long ll;

vector<int>as;
int vis[maxn],vs[maxn],h[maxn],ee=1,st[maxn],top=0,deg[maxn];
struct Edge{
	int v,id,next;
}e[maxn<<1];
struct EDGE{
	int u,v;
}ed[maxn];
void addedge(int u,int v,int id){
	e[ee]=Edge{v,id,h[u]};
	h[u]=ee++;
}
void dfs(int u){
	for(int i=h[u];i;i=h[u]){//这里不能是i=e[i].next,因为同一个点在求解欧拉回路的时候会被多次遍历 
		int id=e[i].id,v=e[i].v;
		h[u]=e[i].next;
		if(vs[id])continue;
		vs[id]=1;
		dfs(v);
		st[++top]=id;
	}
}
void work(){
	int l=1,r=top;
	while(l<r){
		int id=st[l];
		int u=ed[st[l]].u,v=ed[st[l]].v;
		if(deg[u]&1 && deg[v]&1){
			u=ed[st[r]].u,v=ed[st[r]].v;
			id=st[r];
			r--;
		}else l++;
		deg[u]--,deg[v]--;
		as.push_back(id);
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		ed[i]=EDGE{u,v};
		deg[u]++;
		deg[v]++;
		addedge(u,v,i);
		addedge(v,u,i);
	}
	int ans=m;
	for(int i=1;i<=n;++i){
		top=0;
		dfs(i);
		if(top)work(),ans--;
	}
	printf("%dn",ans);
	for(int i=0;i<as.size();++i){
		printf("%d ",as[i]);
	}puts("");
}/*test:
12 16
1 2
2 3
3 4
4 1
1 5
1 9
5 9
2 6
2 10
6 10
3 7
3 11
7 11
4 8
4 12
8 12

*/

最后

以上就是光亮路人为你收集整理的acm-(欧拉回路、思维、好题)2020 ECNU Campus Online Invitational Contest E. Even Degree的全部内容，希望文章能够帮你解决acm-(欧拉回路、思维、好题)2020 ECNU Campus Online Invitational Contest E. Even Degree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。