【JZOJ A组】旅游

Description

Input

Output

Sample Input

6 10
4 6
4 5
3 6
5 2
3 2
1 2
3 4
6 1
2 4
1 3

Sample Output

2132

Data Constraint

思路

如果每条边能走一次就遍历完全图，这个就是欧拉回路。
一个图是欧拉回路当且仅当每个点的度数为偶数。
我们需要计算哪几条边会重复走
如果一条边两端的点的度数为奇数，则一定要重复走

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=6e5+77,mod=998244353;
int n,m,fa[maxn],dis[maxn],ans,list[maxn],cnt,d[maxn];
struct E
{
	int to,next,v;
}e[maxn*3];
int gf(int x)
{
	if(fa[x]==x) return x;else return fa[x]=gf(fa[x]);
}
void add(int u,int v,int val)
{
	e[++cnt].to=v; e[cnt].next=list[u]; list[u]=cnt; e[cnt].v=val;
}
int dfs(int u,int fa)
{
	int s=d[u]%2,s1;
	for(int i=list[u]; i; i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		s1=dfs(v,u);
		if(s1%2==1) ans=(ans+e[i].v)%mod;
		s+=s1;
	}
	return s;
}
int main()
{
	freopen("travel.in","r",stdin); freopen("travel.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) fa[i]=i;
	dis[0]=1; for(int i=1; i<=m; i++) dis[i]=dis[i-1]*2%mod,ans=(ans+dis[i])%mod;
	for(int i=1; i<=m; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int u=gf(x),v=gf(y);
		if(u!=v) add(x,y,dis[i]),add(y,x,dis[i]),fa[u]=fa[v];
		d[x]++,d[y]++;
	}
	dfs(1,0);
	printf("%d",ans);
}