图论 欧拉图_非零度顶点

欧拉图

欧拉路的定义和概念

欧拉回路定义：通过图中每条边恰好一次的回路。
欧拉通路定义：通过图中每条边恰好一次的通路。

欧拉图

定义：具有欧拉回路的图。

无向图是欧拉图，当且仅当：

1. 非零度顶点是连通的
2. 顶点的度数都是偶数

有向图是欧拉图，当且仅当：
4. 非零度顶点是强连通的
5. 每个顶点的入度和出度相等

半欧拉图

具有欧拉通路但不具有欧拉回路的图。

无向图是半欧拉图，当且仅当：

1. 非零度顶点是连通的
2. 恰有$2$个度数为奇数的顶点

有向图是半欧拉图，当且仅当：
3. 非零度顶点是弱连通的
4. 一个顶点的$入度=出度+1$，一个顶点的$出度=入度+1$，其他顶点的入度和出度相等

$\mathrm{Hierholzers}$算法

原理

从任意一个点$u$开始遍历搜索，直到再次到达点$u$，即找到一个环。将此环定义为C，如果环C中存在某个点x，其有出边不在环中，则继续以此点开始遍历，直到图中所有的边均已经添加到环中。
一般而言，我们使用$\mathrm{DFS}$来解决此类问题。

特别注意，在使用$\mathrm{Hierholzers}$算法前，必须先根据上述的性质，判断该图是否存在欧拉回路。

实现

例题1：

[USACO3.3] 骑马修栅栏 Riding the Fences
题目描述
John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。 John 的农场上一共有 $m$
个栅栏，每一个栅栏连接两个顶点，顶点用 $1$ 到 $500$ 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 $1$
个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John
能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。
你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个
$500$ 进制的数，那么当存在多组解的情况下，输出 $500$ 进制表示法中最小的一个
（也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。 输入数据保证至少有一个解。

#include#define INF 0x3f3f3f3fusing namespace std;const int N = 10005;int g[N][N];bool vis[N];int num[N], n, ans[N], cnt;void dfs(int x){for(int y = 1; y <= n; y++)if(g[x][y] >= 1){g[x][y]--;g[y][x]--;dfs(y);}ans[++cnt] = x;}int main(){int F;int start = INF;cin >> F;for(int i = 1; i <= F; i++){int u, v;cin >> u >> v;g[u][v]++;g[v][u]++;num[u]++;num[v]++;n = max(n, max(u, v));start = min(start, min(u, v));}for(int i = start; i <= n; i++)if(num[i] % 2 != 0){start = i;break;}dfs(start);for(int i = cnt; i >= 1; i--) cout << ans[i] << endl;return 0;}

例题2：

UVA10054 The Necklace
题目描述
有一种由彩色珠子连接而成的项链。每个珠子的两半由不同颜色组成。相邻两个珠子在接触的地方颜色相同。现在有一些零碎的珠子，需要确认它们是否可以复原成完整的项链。

#includeusing namespace std;const int N = 60;int du[N], g[N][N], isv[N], ans[5000], sum;void dfs(int u){ for(int i = 1; i <= 50; i++) if(g[u][i] && isv[u] && isv[i]) { g[u][i]--, g[i][u]--, isv[u]--, isv[i]--; dfs(i); ans[sum] = i, ans[sum + 1] = u; sum += 2;}}int main(){int T;cin >> T;int cnt = 1;for(; cnt <= T; cnt++){memset(du, 0, sizeof(du)); memset(ans, 0, sizeof(ans)); memset(g, 0, sizeof(g)); memset(isv, 0, sizeof(isv)); sum = 0; int n, a, b; cin >> n; for(int i = 1; i <= n; i++) { cin >> a >> b; du[a]++, du[b]++; g[a][b]++, g[b][a]++, isv[a]++, isv[b]++;}dfs(a);cout << \"Case #\" << cnt << \"\\n\";for(int i = 1; i <= 50; i++)if(isv[i] || du[i] % 2 == 1){cout << \"some beads may be lost\" << \"\\n\";goto loop;}for(int i = 0; i < sum; i = i + 2) cout << ans[i] << \' \' << ans[i + 1] << \"\\n\";loop:;cout << \"\\n\"; } return 0;}