本文主要是介绍JD 1027：欧拉回路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目：click here~~
题目分析：
若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉(Euler)回路。
具有欧拉路径的图称为欧拉图（简称E图）。
无向图存在欧拉回路的充要条件：
一个无向图存在欧拉回路，当且仅当该图拥有奇数度数的顶点的个数为0且该图是连通图。
有向图存在欧拉回路的充要条件：
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
并查集判断图是否连通 + 判断顶点的度是否为偶数
const int maxn = 1008 ;
int deg[maxn] ;
int fa[maxn] ;
void init(){for(int i = 0;i < maxn;i++)fa[i] = i ;
}int GetFath(int x){if(x == fa[x]) return x ;return fa[x] = GetFath(fa[x]) ;
}void Merg(int u , int v){int fu = GetFath(u) ;int fv = GetFath(v) ;if(fu != fv){fa[fu] = fv ;}
}int main(){int n , m ;while(cin >> n){if(n == 0) break ;cin >> m ;init() ;int a , b , i , j , k ;memset(deg , 0 , sizeof(deg)) ;for(i = 0;i < m;i++){scanf("%d%d",&a,&b) ;deg[a]++ ;deg[b]++ ;Merg(a , b) ;}set<int> s ;for(i = 1;i <= n;i++)s.insert(GetFath(i)) ;if(s.size() != 1){puts("0") ;continue ;}else{for(i = 1;i <= n;i++)if(deg[i]&1) break ;if(i <= n) puts("0") ;else puts("1") ;}}return 0 ;
}这篇关于JD 1027：欧拉回路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
