2025.9.12 欧拉回路

%判定条件%

所有点的度数都是偶数的无向连通图有欧拉回路

有两个点的度数是奇数，其它点都是偶数的无向连通图有欧拉路径

所有点的入度和出度都相等的有向连通图有欧拉回路

有一个点出度比入度大一，有一个点入度比出度大一，其它点的入度和出度都相等的有向连通图有欧拉路径

%寻找方法%

CPP

void dfs(int u){
	for(int i=vis[u];i<e[u].size();i=vis[u]){
		vis[u]=i+1;
		dfs(e[u][i]);
	} 
	ans[++tot]=u;
}

Hierholzer 算法，每次找到一个环，并倒序插入来实现一边 DFS 找环一边插环

为什么要倒序插入可以看下面这张图

文章操作