2020 年 “游族杯” 全国高校程序设计网络挑战赛 E.Even Degree(欧拉回路+欧拉路径性质)

题目

n(1<=n<=5e5)个点，m(0<=m<=5e5)个点的无向图，

保证所有点的度数为偶数，无重边，无自环

每次你可以选择一条边，只要这条边当前连的两个点的度数不同时为奇数，就可删掉这条边

输出最大的删边数k，及删的k条边的编号

思路来源

官方题解

题解

所有点的度数为偶数，说明一定存在欧拉回路

考虑先随便删掉一条边，剩下的转化为起点为奇数，终点为奇数，中间点为偶数的欧拉路径问题

最后一条边一定删不了，然后证剩下的都能删，

如果欧拉路径当前边不均奇，则删掉当前边，

否则有当前点和下一个点（如代码中被注释掉的样例）度同为奇数，

则下一个点和下下个点不同时为奇数（由于无重边，是三个不同的点，否则不满足欧拉路径0/2奇度点要求）

则先删下一条边，再删当前这条边，然后沿欧拉路径继续走即可，

可取完除了最后一条边的所有边

注意图不一定连通，所以对每个分量这么删

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<set>
using namespace std;
typedef pair<int,int> P;
const int N=5e5+10;
vector<P>e[N];
P f[N];
bool vis[N],used[N];
int now[N],ans[N],cnt,res[N],tot;
int n,m,u,v;
void dfs(int u){
	used[u]=1;
	while(now[u]<e[u].size()){
		int v=e[u][now[u]].first,id=e[u][now[u]].second;
		now[u]++;
		if(vis[id])continue;
		vis[id]=1;
		dfs(v);
		ans[++cnt]=id;
	}
}
int ano(int x,int id){
    return f[id].first^f[id].second^x;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		f[i]=P(u,v);
		e[u].push_back(P(v,i));
		e[v].push_back(P(u,i));
	}
    for(int i=1;i<=n;++i){
        if(!e[i].size())continue;
        if(!used[i]){
            cnt=0;
            dfs(i);
            int now=i,nex=ano(i,ans[1]);
            res[++tot]=ans[1];
            for(int j=2;j<cnt;++j){
                if(ano(nex,ans[j])==now){
                    res[++tot]=ans[j+1];
                    res[++tot]=ans[j];
                    nex=ano(now,ans[j+1]);//连走两条边
                    j++;
                }
                else{
                    res[++tot]=ans[j];
                    nex=ano(nex,ans[j]);
                }
            }
        }
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;++i){
        printf("%d%c",res[i]," \n"[i==tot]);
    }
	return 0;
}
/*
5 7
1 3
1 4
1 5
1 2
2 3
2 4
2 5
*/