本文主要是介绍HDU 1879 欧拉回路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
判断一个图是否是欧拉回路。
补充：
欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。
欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路。
无向图是否具有欧拉通路或回路的判定:
欧拉通路:图连通；图中只有0个或2个度为奇数的节点
欧拉回路:图连通；图中所有节点度均为偶数
有向图是否具有欧拉通路或回路的判定:
欧拉通路:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1 或 所有节点入度等于出度
欧拉回路:图连通；所有节点入度等于出度
这道题的算法思路：利用并查集先判断图连通性，然后利用in数组记录各点的度。（因为该题是无向图）
判断条件：当一个点的根节点与其他点的根节点不等，则不连通，则返回0；当该点的度数是奇数时则非欧拉图，返回0；其他情况返回1
代码：#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
//判断连通性，然后判断度相同
int IN[1001];//入度
int par[1001],n,m;
int find(int x);
void unite(int x, int y);
int find(int x) {return par[x] == x ? x : par[x] = find(par[x]);
}void unite(int x, int y) {x = find(x);y = find(y);if(x == y) return;par[x] = y;}
int main(){while(~scanf("%d",&n),n){memset(IN,0,sizeof(IN));for(int i=1;i<=n;i++){par[i]=i;//多个等号啊！！！！ }scanf("%d",&m);for(int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);unite(a, b);IN[a]++; IN[b]++;}int flag=1;int temp=find(1);for(int i=1;i<=n;i++){if(IN[i] & 1)flag=0;if(find(i)!=temp)flag=0;}printf("%d\n",flag);} return 0;
}这篇关于HDU 1879 欧拉回路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
