【HDU】1878 欧拉回路题解（并查集 + 无向图欧拉回路）

- 日理万妓 2023-07-14 10:54 9阅读 0赞

> 原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1878][http_acm.hdu.edu.cn_showproblem.php_pid_1878]

**思路：** 一道判断无向图中是否存在欧拉回路的简单题。

*  判断欧拉回路（起点、终点为同一个点）的方法：
    
    1.无向图中：所给定的图为连通图，且所有节点的度为偶数；
    
    2.有向图中：所给定的图为连通图，且所有节点的度为零。
 *  判断欧拉路（起点、终点不在同一个点）的方法：
    
    1.无向图中：所给定的图为连通图，且只有两个结点的度数为奇数（即起点和终点）
    
    2.有向图中：所给定的图为连通图，且除了一个结点度数为 -1（终点），一个结点度数为 1 （起点）外，其他所有节点的度都为零。

**Code：**

#include <iostream>
    #include <cstring>
    using namespace std;
    int n,m;
    int d[1010],fa[1010];
    void init(){ 
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;i++)
            fa[i]=i;
    }
    int find(int x){ 
        if(fa[x]==x)    return x;
        else    return fa[x]=find(fa[x]);
    }
    int main(){ 
        while(cin>>n>>m){ 
            if(!n)  break;
            init();
            for(int i=1;i<=m;i++){ 
                int u,v;    cin>>u>>v;
                d[u]++,d[v]++;
                int fx = find(u);
                int fy = find(v);
                if(fx!=fy)
                    fa[fx]=fy;
            }
            int cnt1=0,cnt2=0;
            for(int i=1;i<=n;i++){ 
                if(d[i]%2==0)   cnt1++;
                if(fa[i]==i)    cnt2++;
            }
            if(cnt1==n && cnt2==1)
                cout<<1<<endl;
            else
                cout<<0<<endl;
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1878]: http://acm.hdu.edu.cn/showproblem.php?pid=1878