如何做好公司网站建设/市场营销比较好写的论文题目

【题目链接】

ybt 1341：【例题】一笔画问题

【题目考点】

1. 图论：欧拉回路

求解欧拉回路使用Hierholzer算法
复杂度：$O(V+E)$

【解题思路】

• 无向图有欧拉回路的条件：所有顶点的度都是偶数。
• 无向图有欧拉路径的条件：有两个顶点的度是奇数，其余顶点的度都是偶数。

该题默认一定有欧拉路径或欧拉回路。
遍历选择起始顶点，如果v的度为奇数，那么选择该顶点为起始顶点。否则起始顶点默认为1号顶点。
使用Hierholzer算法可以在$O(V+E)$的时间复杂度内求出欧拉回路。
顶点数n最大为100，可以使用邻接矩阵或邻接表解决。

【题解代码】

解法1：邻接矩阵

#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, edge[N][N], deg[N];//n:顶点数 m:边数 deg[i]:顶点i的度 
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{for(int v = 1; v <= n; ++v){if(edge[u][v]){edge[u][v] = edge[v][u] = 0;dfs(v);        }}stk.push(u);
}
int main()
{int st = 1, f, t;//st:起点 cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t;edge[f][t] = edge[t][f] = 1;deg[f]++, deg[t]++;}for(int v = 1; v <= n; ++v)//如果找到奇数度顶点，就从奇数度顶点出发，否则从1出发 {if(deg[v] % 2 == 1){st = v;break;}}dfs(st);while(stk.empty() == false){cout << stk.top() << ' ';stk.pop();}return 0;
}

解法2：邻接表

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define M 2005
struct Node
{int v, e;//v:顶点编号 e：边的编号 Node(){}Node(int a, int b):v(a), e(b){}
};
int n, m, deg[N], beg[N];//n:顶点数 m:边数 deg[i]:顶点i的度 beg[i]：顶点i的邻接点从edge[beg[i]]开始算起，前面的相当于删掉了。 
vector<Node> edge[N];
bool vis[M];
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{for(int &i = beg[u]; i < edge[u].size(); ++i)//i是beg[u]的引用，++i相当于++beg[u]，这样在下一次访问顶点u的邻接点时，只需要从下标beg[u]开始看起，前面的当做已经被删掉了{int v = edge[u][i].v, e = edge[u][i].e;if(vis[e] == false){vis[e] = true;dfs(v);}}stk.push(u);
}
int main()
{int st = 1, f, t;//st:起点 cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t;edge[f].push_back(Node(t, i));edge[t].push_back(Node(f, i));deg[f]++, deg[t]++;}for(int v = 1; v <= n; ++v)//如果找到奇数度顶点，就从奇数度顶点出发，否则从1出发 {if(deg[v] % 2 == 1){st = v;break;}}dfs(st);while(stk.empty() == false){cout << stk.top() << ' ';stk.pop();}return 0;
}