题目链接：点击打开链接
题目大意：略。
解题思路：并查集 + 顶点度数偶数判断。
如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。
具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
1、无向图存在欧拉回路的充要条件：
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。
2、有向图存在欧拉回路的充要条件：
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1010; int n,m; int pre[maxn], vis[maxn][maxn], deg[maxn]; void init() { for(int i=1;i<=n;i++) pre[i]=i; mem(vis,0); mem(deg,0); } int find(int x) { return pre[x]==x?x:pre[x]=find(pre[x]); } int main() { while(~scanf("%d%d",&n,&m)) { init(); int u,v; for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); if(!vis[u][v]) { vis[u][v]=vis[v][u]=1; deg[u]++, deg[v]++; } pre[find(u)]=pre[find(v)]; // 合并为同一个根 } int cnt=0; for(int i=1;i<=n;i++) { if(pre[i]==i) // 统计 root 结点个数 { cnt++; if(cnt>1) break; } if(deg[i]%2!=0) // 必须所有顶点度数都为偶数 { cnt=-1; break; } } puts(cnt==1?"1":"0"); } return 0; }
