1 基础概念
- 欧拉回路:每条边只经过一次,而且回到起点
- 欧拉路径:每条边只经过一次,不要求回到起点
- 欧拉回路判断:
- 无向图:连通(不考虑度为 0 的点),没有奇度顶点
- 有向图:强连通,每个顶点出度等于入度
- 混合图(有无向边和有向边):首先是基图连通(不考虑度为 0 的点),然后需要借助网络流判定。
- 首先给原图中的每条无向边随便指定一个方向(称为初始定向),将原图改为有向图 G’,然后的任务就是改变 G’ 中某些边的方向(当然是无向边转化来的,原混合图中的有向边不能动)使其满足每个点的入度等于出度。
- 设 D[i] 为 G’ 中 (点 i 的出度 - 点 $i $的入度)。可以发现,在改变 G’ 中边的方向的过程中,任何点的 D 值的奇偶性都不会发生改变(设将边 <i,j> 改为 <j,i>,则 $i 入度加 1 出度减 1,j$ 入度减 1 出度加 1,两者之差加 2 或减 2,奇偶性不变)!而最终要求的是每个点的入度等于出度,即每个点的 D 值都为 0,是偶数,故可得:若初始定向得到的 G’ 中任意一个点的D值是奇数,那么原图中一定不存在欧拉环!
- 若初始 D 值都是偶数,则将 G’ 改装成网络:设立源点 S 和汇点 T,对于每个 D[i]>0 的点i,连边 <S,i>,容量为 D[i]/2;对于每个 D[j]<0 的点 j,连边 <j,T>,容量为 −D[j]/2; G’中的每条边在网络中仍保留,容量为 1(表示该边最多只能被改变方向一次)。求这个网络的最大流,若 S 引出的所有边均满流,则原混合图是欧拉图,将网络中所有流量为 1 的中间边(就是不与 S 或 T关联的边)在 G’ 中改变方向,形成的新图 G” 一定是有向欧拉图;若 S 引出的边中有的没有满流,则原混合图不是欧拉图。
- 欧拉路径的判断:
- 无向图:连通(不考虑度为 0 的点),没有奇度顶点或恰有两个奇度顶点
- 有向图:基图连通(把边当成无向边,同样不考虑度为 0 的点),每个顶点出度等于入度或
者有且仅有一个点的出度比入度多 1,有且仅有一个点的出度比入度少 1,其余出度等于入
度。
- 混合图:如果存在欧拉回路,一定存在欧拉路径了。否则如果有且仅有两个点的(出度 -入
度)是奇数,那么给这个两个点加边,判断是否存在欧拉回路。
https://blog.csdn.net/richenyunqi/article/details/80382450/
欧拉路径模板
1 递归
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 39 40 41 42 43
| #include<bits/stdc++.h> using namespace std;
const int maxn = 1e4+5; vector<int>graph[maxn],path; int N, M; bool visit[maxn][maxn];
bool f(vector<int>&v){ return v.size()%2==1; }
void DFS(int v){ for(int i=0;i<graph[v].size();++i){ int w=graph[v][i]; if(!visit[v][w]){ visit[v][w]=visit[w][v]=true; DFS(w); } } path.push_back(v); } int main(){ scanf("%d%d",&N,&M); for(int i=0;i<M;++i){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); graph[b].push_back(a); } for(int i=1;i<=N;++i) sort(graph[i].begin(),graph[i].end()); DFS(1); int k=count_if(graph+1,graph+N+1,f); if(path.size()==M+1&&(k==0||(k==2&&f(graph[1])))) for(int i=path.size()-1;i>=0;--i) printf("%d ",path[i]); else printf("-1"); return 0; }
|
2 非递归
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 39 40 41 42 43 44 45 46 47 48
| #include<bits/stdc++.h> using namespace std;
const int maxn = 1e4+5; vector<int>graph[maxn],path; int N, M; bool visit[maxn][maxn];
bool f(vector<int>&v){ return v.size()%2==1; } int main(){ scanf("%d%d",&N,&M); for(int i=0;i<M;++i){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); graph[b].push_back(a); } for(int i=1;i<=N;++i) sort(graph[i].begin(),graph[i].end()); stack<int>s; s.push(1); while(!s.empty()){ int v=s.top(),i; for(i=0;i<graph[v].size();++i){ int w=graph[v][i]; if(!visit[v][w]){ s.push(w); visit[v][w]=visit[w][v]=true; break; } } if(i==graph[v].size()){ path.push_back(v); s.pop(); } } int k=count_if(graph+1,graph+N+1,f); if(path.size()==M+1&&(k==0||(k==2&&f(graph[1])))) for(auto i=path.rbegin();i!=path.rend();++i) printf("%d ",*i); else printf("-1"); return 0; }
|