欧拉回路是经过所有边仅一次
无向图有欧拉回路的条件是:每个点的度数都是偶数 并且图连通（可以有孤立点）
#include <cstdio>
#define N 1000007
int f[N],I[N],d[N],n,m,u,v,A;
int F(int x) {return x==f[x]?x:f[x]=F(f[x]);}
int main() {
d[1]=2;//孤立点不需要连边 但一定要经过1号点 这样做是区别1和孤立点
//答案是奇度点个数+不含奇度点的连通块个数
//每个连通块一定有偶数个奇度点,直接连到1上就可以保证图连通,不含奇度点的连通块
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)f[i]=i;
while (m--)scanf("%d%d",&u,&v),++d[u],++d[v],f[F(u)]=F(v);
for (int i=1;i<=n;++i)if(d[i]&1)I[F(i)]=1,++A;//I[i]表示i所在的连通块是否有奇度点
for (int i=1;i<=n;++i)if(f[i]==i&&d[i]&&!I[i])++++A;//每个没有奇度点的连通块额外需要一条边
/*
4
1 2
2 1
3 4
4 3
为了便于计算 可以理解为(1,2)和(3,4)各需要一条边
*/
printf("%d",!I[F(1)]&&2==A?0:A/2);//如果1所在连通块没有奇度点并且没有其他边(A==2就是只有1所在连通块"需要"的那条边) 那么答案是0
return 0;
}CodeForces 209C Trails and Glades[构造]
原文：https://www.cnblogs.com/storz/p/10463442.html