如何用c语言或c++判断是否是欧拉回路

Python021

如何用c语言或c++判断是否是欧拉回路,第1张

一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图

一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图

可以用邻接矩阵或者邻接表,做一次DFS或者BFS访问各个节点判断入度出度就行

使用并查集,每个讲克鲁斯卡尔的算法都会涉及并查集。

初始为每个顶点属于互不相同的集合,当添加一条边时,就把这两条边的顶点加入到同一集合。如果边的两顶点属于不同集合,就可以添加这条边,否则就不可以添加(会构成回路)。

对于集合的操作,有子集的划分。前几天的天津还是哪个regional网络预赛,就有个子集划分的题目。