欧拉回路裸题，给定n个点和m条有向边，判断该图是否为欧拉回路
有向图欧拉回路判断条件有：图连通，所有点的度为偶数
代码一，用并查集来判断图是否连通，然后逐一扫描所有点的度是否为偶数
#include#include #define N 110int n,m;int d[N];int p[N];int find(int x) //并查集{ return p[x]==x ? x : find(p[x]); }int main(){ int CASE,i,j,u,v,x,y,ok; scanf("%d",&CASE); while(CASE--) { scanf("%d%d",&n,&m); memset(d,0,sizeof(d)); for(i=1; i<=n; i++) p[i]=i; for(i=1; i<=m; i++) { scanf("%d%d",&u,&v); d[u]++; d[v]++; x=find(u); y=find(v); if(x!=y) p[u]=v; }// for(i=1; i<=n; i++) printf("%d ",find(i)); printf("\n"); for(ok=1,i=1 ;i
代码二，直接用邻接矩阵来建图，然后dfs整个图看有多少个连通分量，当只有一个连通分量时说明图连通，然后再逐一判断所有点的度是否为偶数
#include#include #define N 110bool g[N][N],vis[N];int d[N];int n,m;void dfs(int i){ int j; for(j=1; j<=n; j++) if( g[i][j] && !vis[j]) { vis[j]=1; dfs(j); } }int main(){ int T,i,u,v,count; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); for(i=1; i<=m; i++) { scanf("%d%d",&u,&v); g[u][v]=1; d[u]++; d[v]++; } for(count=0,i=1; i<=n; i++) if(!vis[i]) { ++count; vis[i]=1; dfs(i);} if(count>1) printf("no\n"); else { for(i=1; i<=n; i++) if( d[i]%2 ) break; if(i>n) printf("yes\n"); else printf("no\n"); } } return 0;}