订阅更新(RSS/Atom): 定义欧拉回路：通过图中每条边恰好一次的回路欧拉通路（欧拉路径）：通过图中每条边恰好一次的通路欧拉图：具有欧拉回路的图半欧拉图：具有欧拉通路但不具有欧拉回路的图无向图是欧拉图当且仅当：非零度顶点是连通的顶点的度数都是偶数无向图是半欧拉图当且仅当：非零度顶点是连通的恰有 0 或 2 个奇度顶点有向图是欧拉图当且仅当：非零度顶点是强连通的每个顶点的入度和出度相等有向图是半欧拉图当且仅当：非零度顶点是弱连通的至多一个顶点的出度与入度之差为 1 至多一个顶点的入度与出度之差为 1 其他顶点的入度和出度相等弱连通：将所有有向边替换为无向边后，整张图连通。 Hierholzer 算法的具体步骤：遍历当前节点的所有出边，并 DFS 访问相邻顶点，将经过的边删掉。遍历完所有出边后，将 $u$ 加入栈中。最后把栈中的顶点反过来，再输出，就是欧拉回路。如果要求字典序最小，只需在一开始对每个点的所有出边从小到大排序。这样一来，欧拉回路上从左往右看，每个点的后继都取到了理论最小值。对于无向图和有向图的欧拉路径，必须从奇点或唯一的出度比入度大 1 的点开始 dfs。 Luogu-P7771 【模板】欧拉路径实现时，要注意一个小细节：用 hd[x] 数组记录节点 $x$ 目前删到了哪条边，每次走过一条边时要 hd[x]++，然后下次到达这个点时再调用这个值。否则的话，每次到了这个点都要从 0 开始判断这些边是否被删除掉，会超时。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; const int N = 2e5+5; int n, m, S, top, sta[N], in[N], hd[N]; vector e[N]; void dfs(int u) { for (int &i = hd[u]; i < e[u].size(); ) { // 细节 dfs(e[u][i++]); } sta[++top] = u; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; e[u].push_back(v); in[v]++; } for (int i = 1; i <= n; i++) { sort(e[i].begin(), e[i].end()); if (abs((int)e[i].size()-in[i]) > 1) { puts("No"); return 0; } if (e[i].size() > in[i]) { if (S) { puts("No"); return 0; } else S = i; } } dfs(S ? S : 1); if (top != m+1) puts("No"); else { reverse(sta+1, sta+top+1); for (int i = 1; i <= top; i++) { cout << sta[i] << " "; } } return 0; } Luogu-P1341 无序字母对：把每个字符当做一个点，把输入的字符串看做两个字符间可以连一条边，最后要求的字符串就是找一笔画，即欧拉回路（路径）。要判断图是否连通。 Luogu-P1127 词链：与上一道题类似 ABC286G Unique Walk：对于非关键边，走多少次都无所谓，可以把非关键边形成的连通块缩成一个点，然后再判欧拉路初级图论 - qAlex_Weiq - 博客园欧拉图 - OI Wiki

欧拉回路笔记

剩余内容已隐藏查看完整文章以阅读更多

剩余内容已隐藏
查看完整文章以阅读更多