欧拉图
讲的比较好的博客：https://www.cnblogs.com/zdblog/articles/3725858.html
文章目录
预备知识点
欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路
欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路
有向图的基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图
具有欧拉回路的无向图G成为欧拉图。
无向图
定理
无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点或者无奇度结点。
推论
- 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点；
- 当G是无奇度结点的连通图时，G必有欧拉回路；
- G为欧拉图（存在欧拉回路）的充分必要条件是 G为无奇度结点的连通图；
有向图
定理
有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与入度相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1.
推论
- 当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点；
- 当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路；
- 有向图D为有向欧拉图的充要条件是 D的基图为连通图，并且所有顶点的出、入度都相等。
有向图和无向图大体一致，核心点都在于入读为奇数的点的个数为0或2。
模板题
题目链接
洛谷 P1341
题意
给定一个无向图，要求一个字典序最小的欧拉回路。
如果不存在欧拉通路，输出“No Solution”。
题解
根据这是一个无向图，直接用邻接矩阵存图，然后计算每个顶点的度。
如果存在欧拉通路的话，那么度数为奇的点数量肯定为0或2。
0的情况：整张图是一个环，直接让起点的字典序相对小即可；
2的情况: 出发点只有可能是2个，那么这2个点字典序哪个小就从哪开始。
求欧拉通路序列的方法：dfs遍历，走过的边删边处理即可（详情见代码)。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n,m,cnt[maxn],g[maxn][maxn],a,b;
string s;
vector<int> e[maxn],path;
bool v[maxn],flag;
bool check() {
int res = 0;
for(int i=1;i<=52;i++) {
if(cnt[i]&1) res++;
}
if(res==2) {
for(int i=1;i<=52;i++) {
flag = 0;
if(cnt[i]&1) {
a = i;
break;
}
}
}
if(res==0) {
for(int i=1;i<=52;i++) {
flag = 1;
if(cnt[i]) {
a = i;
break;
}
}
}
if(res==2 || res==0) return true;
return false;
}
void dfs(int x) {
for(int i=1;i<=52;i++) {
if(g[x][i]) {
g[x][i] = g[i][x] = 0;
dfs(i);
}
}
path.push_back(x);
}
char exec(int x) {
if(x>=1 && x<=26)
return 'A'+x-1;
return 'a' + (x-26) -1;
}
int main() {
cin>>m;
for(int i=0;i<m;i++) {
cin>>s;
int x,y;
if(s[0]>='a' && s[0]<='z') {
x = s[0]-'a' + 26;
}
else {
x = s[0]-'A';
}
if(s[1]>='a' && s[1]<='z') {
y = s[1]-'a' + 26;
}
else {
y = s[1]-'A';
}
x++, y++;
g[x][y] = g[y][x] = 1;
cnt[x]++, cnt[y]++;
}
if(!check()) {
cout<<"No Solution"<<endl;
return 0;
}
dfs(a);
reverse(path.begin(),path.end());
for(int i=0;i<path.size();i++) {
cout<<exec(path[i]);
}
return 0;
}