企业官网建设流程全解析

【题目来源】
https://www.luogu.com.cn/problem/U308246

【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
输入一个无向图，根据一笔画的两个定理，如果寻找欧拉回路，对一号点执行深度优先遍历；找欧拉路，则对最后一个奇点执行 dfs，时间复杂度为 O(m+n)，m 为边数，n 是点数。

【输入格式】
第一行 n，m，有 n 个点，m 条边，以下 m 行描述每条边连接的两点。

【输出格式】
欧拉路或欧拉回路，输出一条路径即可。要求从小到大顺序搜索，如果有奇点从编号大的奇点开始，否则从 1 开始搜索，回溯时存储输出。

【输入样例】
5 5
1 2
2 3
3 4
4 5
5 1

【输出样例】
1 5 4 3 2 1

【数据范围】
对于 100% 的数据：1<n<100，1<m<2000。

【算法分析】
● 欧拉路径与欧拉回路定义
图中经过所有边恰好一次的路径称为欧拉路径（也就是一笔画）。
如果此路径的起点和终点相同，则称其为欧拉回路。
注意：若存在欧拉回路，则一定存在欧拉路径。

● 欧拉路径判定
（1）有向图欧拉路径：图中恰好存在 1 个结点的出度比入度多 1（这个结点即为起点 S），1 个结点的入度比出度多 1（这个结点即为终点 T），其余结点的出度=入度。
（2）有向图欧拉回路：所有结点的入度=出度（起点 S 和终点 T 可以为任意点）。
（3）无向图欧拉路径：图中恰好存在 2 个结点的度是奇数，其余结点的度为偶数，这两个度为奇数的结点即为欧拉路径的起点 S 和终点 T。
（4）无向图欧拉回路：所有结点的度都是偶数（起点 S 和终点 T 可以为任意结点）。

【算法代码：dfs】

#include<bits/stdc++.h> using namespace std; const int N=105; int g[N][N]; int du[N],path[N]; int n,m; int tot; void dfs(int i) { for(int j=1; j<=n; j++) { if(g[i][j]==1) { g[i][j]=g[j][i]=0; dfs(j); } } path[++tot]=i; } int main() { memset(g,0,sizeof g); memset(du,0,sizeof du); cin>>n>>m; while(m--) { int x,y; cin>>x>>y; g[x][y]=g[y][x]=1; du[x]++,du[y]++; } //Start from odd point with max id vector<int> odd; for(int i=1; i<=n; i++) { if(du[i]%2==1) odd.push_back(i); } int start=1; if(!odd.empty()) { sort(odd.begin(),odd.end()); start=odd.back(); //odd point with max id } tot=0; dfs(start); for(int i=1; i<=tot; i++) { cout<<path[i]<<" "; } return 0; } /* in: 5 5 1 2 2 3 3 4 4 5 5 1 out: 1 5 4 3 2 1 */

【算法代码：bfs】

#include<bits/stdc++.h> using namespace std; const int N=105; vector<int> g[N]; vector<int> path; int du[N]; bool st[N][N]; stack<int> stk; int n,m; void bfs(int start) { //hierholzer stk.push(start); while(!stk.empty()) { int t=stk.top(); bool flag=false; for(int i=0; i<g[t].size(); i++) { int j=g[t][i]; if(!st[t][j]) { st[t][j]=st[j][t]=true; stk.push(j); flag=true; break; } } if(!flag) { stk.pop(); path.push_back(t); } } } int main() { memset(st,false,sizeof st); cin>>n>>m; while(m--) { int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); du[a]++,du[b]++; } for(int i=1; i<=n; i++) { sort(g[i].begin(),g[i].end()); } //Start from odd point with max id vector<int> odd; for(int i=1; i<=n; i++) { if(du[i]%2==1) odd.push_back(i); } int start=1; if(!odd.empty()) { sort(odd.begin(),odd.end()); start=odd.back(); //odd point with max id } bfs(start); for(int i=0; i<path.size(); i++) { cout<<path[i]<<" "; } return 0; } /* in: 5 5 1 2 2 3 3 4 4 5 5 1 out: 1 5 4 3 2 1 */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/140747624
https://blog.51cto.com/u_14932227/6041733