欧拉回路学习总结
设G = (V, E)是一个图。
欧拉回路 图G中经过每条边一次并且仅一次的回路称作欧拉回路。
欧拉路径 图G中经过每条边一次并且仅一次的路径称作欧拉路径。
欧拉图 存在欧拉回路的图称为欧拉图。
半欧拉图 存在欧拉路径但不存在欧拉回路的图称为半欧拉图。
思想：
首先明确一点，如果原图存在孤立点，那么我们去除孤立点不会对答案有所影响，然后我们来看下面的定理。
定理1 无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。
推论1 无向图G为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。
定理2 有向图G为欧拉图，当且仅当G的基图（即将所有的有向边改为无向边所成的图）连通，且所有顶点的入度等于出度。
推论2 有向图G为半欧拉图，当且仅当G的基图连通，且存在顶点u 的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。
显然，证明什么的我是不会的（有没有发现向小时候的一笔画，其实就是·····）
时间复杂度：
直接 dfs 便利即可，所以复杂度为线性。
适用例题：
uoj 117
分析：欧拉回路 板子题，我就不说多了。
Source：
#include #include #include #include #include #include #include using namespace std; const int MAXM = + 50; const int MAXN = + 50; inline void R(int &v) { char c = 0; bool p = true; v = 0; while(!isdigit(c)) { if(c == '-') p = false; c = getchar(); } while(isdigit(c)) { v = (v << 3) + (v << 1) + (c ^ '0'); c = getchar(); } if(!p) v = -v; } int first[MAXN], tot = 1, t, n, m, x, y; int ans[MAXM], top, id[MAXN], od[MAXN]; bool vis[MAXM]; struct node { int next, to; } edge[MAXM]; inline void create(int x, int y) { tot++, edge[tot].next = first[x], first[x] = tot, edge[tot].to = y; } void read() { R(t), R(n), R(m); for(int i = 1; i <= m; ++i) { R(x), R(y), create(x, y); if(t == 1) create(y, x); od[x]++, id[y]++; } } void dfs(int cur) { //cout << cur << '\n'; for(int &p = first[cur]; p; p = edge[p].next) { int judge = (t == 1 ? (p / 2) : (p - 1)); bool sig = p & 1; if(vis[judge]) continue; //cout << cur << " " << edge[p].to << '\n'; vis[judge] = true, dfs(edge[p].to); if (cur == 1) cout << "top" << top << endl; top++, ans[top] = ((t == 1) ? (sig ? -judge : judge) : judge); } } void work() { if(t == 1) { for(int i = 1; i <= n; ++i) if((id[i] + od[i]) & 1) cout << "NO", exit(0); } else { for(int i = 1; i <= n; ++i) if(id[i] != od[i]) cout << "NO", exit(0); } for(int i = 1; i <= n ; ++i) if(first[i]) { dfs(i); break; } if(top != m) cout << "NO", exit(0); cout << "YES" << '\n'; for(int i = m; i >= 1; --i) cout << ans[i] << " "; } int main() { read(); work(); return 0; } 
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219695.html原文链接：https://javaforall.net
