欧拉回路的判断_欧拉回路判断代码

最近多校碰到几道和欧拉回路相关的题目，这里做个总结

代码：dfs 递归实现：如果是欧拉回路，则输出“1”，否则输出“0”。

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
 
int G[N][N];///邻接矩阵存储图
int vis[N];///遍历时标记该点是否被访问过
int deg[N];///存储节点的度
 
void dfs(int v,int n){///深度优先遍历，递归
    vis[v]=1;
    for(int i=1; i<=n; ++i){
        if(G[v][i]&&!vis[i]) dfs(i,n);
    }
}
 
void init(){
    memset(G,0,sizeof(G));
    memset(vis,0,sizeof(vis));
    memset(deg,0,sizeof(deg));
}
 
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&n){
        init();
        int flag=1;
        for(int i=0; i<m; ++i){
            int u,v;scanf("%d %d",&u,&v);
            G[u][v]=G[v][u]=1;deg[u]++;deg[v]++;
        }
        dfs(1,n);///从第一个顶点搜索
        for(int i=1; i<=n; ++i){
            if(!vis[i]){
                flag=0;///若有点未曾被访问，即一次深度遍历有未访问的点，则不存在欧拉回路
                break;
            }
            if(deg[i]&1){
                flag=0;///若有点的度不是偶数，则不存在欧拉回路
                break;
            }
        }
        if(flag) puts("1");
        else puts("0");
    }return 0;
}
 
  并查集：
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
 
int deg[N],fa[N];
int t,n,m;
int Find(int x){
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
void Union(int x,int y){
    int fx=Find(x);int fy=Find(y);
    if(fx!=fy) fa[x]=fy;
}
bool solve(){
    int cnt=0;
    for(int i=1; i<=n; ++i){
        if(fa[i]==i) cnt++;
    }
    if(cnt!=1) return false;
    for(int i=1; i<=n; ++i){
        if(deg[i]&1) return false;
    }
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n){
        for(int i=1; i<=n; ++i) {fa[i]=i,deg[i]=0;}
        int u,v;
        for(int i=0; i<m; ++i){
            scanf("%d%d",&u,&v);Union(u,v);deg[u]++;deg[v]++;
        }
        if(solve()) puts("1");
        else puts("0");
    } return 0;
}