欧拉路径
从某一点出发经过一条不间断的路径，这条路径刚好访问整个图的所有边一次且仅一次。
欧拉回路
首尾相连的欧拉路径，(一点出发后，最后返回自身)
欧拉图
具备欧拉回路的图
性质：
- 无向图： 各点度数均为偶数
- 有向图： 各点入度与出度相等
半欧拉图
具有欧拉路径，但不具有欧拉回路的图
性质：
- 无向图： 有且仅有两个顶点的度数为奇数
- 有向图： 仅存在一个顶点： 入度 - 出度 = 1， 另一点： 出度 - 入度 = 1
如何找到一条欧拉路径
- 找到一点作为出发点
（对于欧拉回路，我们可以随机选择一个顶点作为起点，然后按照欧拉回路的规则进行遍历，最终形成回路。
对于欧拉路径，我们需要选择一个度数为奇数的顶点作为起点，这样可以保证在遍历的过程中，每个边都被经过一次。如果选择一个度数为偶数的顶点作为起点，那么必然会有一个边被遍历两次，无法形成欧拉路。） - 以出发点进行遍历，每找到一条相连的边，将这条边断开，并将其作为新出发点
- 若某点遍历发现已经无边，将该点入栈。
题目背景
Farmer John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
题目描述
John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。
John 的农场上一共有 \(m\) 个栅栏，每一个栅栏连接两个顶点，顶点用 \(1\) 到 \(500\) 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 \(1\) 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。
你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 \(500\) 进制的数，那么当存在多组解的情况下，输出 \(500\) 进制表示法中最小的一个 （也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。
输入数据保证至少有一个解。
输入格式
第一行一个整数 \(m\)，表示栅栏的数目。
从第二行到第 \((m+1)\) 行，每行两个整数 \(u,v\)，表示有一条栅栏连接 \(u,v\) 两个点。
输出格式
共 \((m+1)\) 行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。
数据保证至少有一组可行解。
样例 #1
样例输入 #1
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
样例输出 #1
1
2
3
4
2
5
4
6
5
7
提示
对于 \(100\%\) 的数据，\(1 \leq m \leq 1024,1 \leq u,v \leq 500\)。
题目翻译来自NOCOW。
分析：
利用vector存图，可以方便的了解某点连了几条边
本题是无向图，且有重边
需要升序排列
本题不清楚有多少个点，需要自行找出
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e3 + 50;
vector<int> v[N];
int n,m,num;
int edge[N][N];
int ans[N];
bool flag;
void dfs(int x)
{
for(int i = 0; i < v[x].size(); i ++)
{
if(edge[x][v[x][i]] > 0)
{
edge[x][v[x][i]]--;
edge[v[x][i]][x]--;
dfs(v[x][i]);
}
}
ans[num] = x;
num++;
}
int main()
{
scanf("%d",&m);
for(int i = 1; i <= m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
edge[x][y]++;
edge[y][x]++;
n = max(n, max(x,y));
}
for(int i = 1; i <= n; i++)
sort(v[i].begin(),v[i].end());
for(int i = 1; i <= n; i++)
{
if(v[i].size() % 2)
{
dfs(i);
flag = true;
break;
}
}
if(!flag)
for(int i = 1; i <= n; i++)
{
if(v[i].size())
{
dfs(i);
break;
}
}
for(int i = num - 1; i >= 0; i --)
printf("%d\n",ans[i]);
return 0;
}
P1341 无序字母对
题目描述
给定 \(n\) 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有 \((n+1)\) 个字母的字符串使得每个字母对都在这个字符串中出现。
输入格式
第一行输入一个正整数 \(n\)。
第二行到第 \((n+1)\) 行每行两个字母，表示这两个字母需要相邻。
输出格式
输出满足要求的字符串。
如果没有满足要求的字符串，请输出 No Solution。
如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。
样例 #1
样例输入 #1
4
aZ
tZ
Xt
aX
样例输出 #1
XaZtX
提示
不同的无序字母对个数有限，\(n\) 的规模可以通过计算得到。
分析：
- 把每个字母对看成一条边，无序字母对看成无向边
- 题目要求变成每条边都必须出现，即欧拉路径，利用其性质判断是否输出No Solution
- 输出字典序最小的方案，需要对同一点的边排序，按照升序sort
- 利用Ascii 编码将字母转化数字，最后输出字母即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e3 + 50;
int m,num,cnt;
bool flag;
int ans[N];
char op[N];
vector<int> v[N];
int edge[N][N];
void dfs(int x)
{
for(int i = 0; i < v[x].size(); i ++)
{
int y = v[x][i];
if(edge[x][y] > 0)
{
edge[x][y]--;
edge[y][x]--;
dfs(y);
}
}
num++;
ans[num] = x;
}
int main()
{
scanf("%d",&m);
for(int i = 1; i <= m; i++)
{
scanf("%s",op);
int x = (int)op[0];
int y = (int)op[1];
v[x].push_back(y);
v[y].push_back(x);
edge[x][y]++;
edge[y][x]++;
}
for(int i = 65; i <= 122; i++)
{
sort(v[i].begin(),v[i].end());
if(v[i].size() % 2) cnt++;
}
if(cnt > 2) {
printf("No Solution");
return 0;
}
for(int i = 65; i <= 122; i++)
{
if(v[i].size() % 2)
{
dfs(i);
flag = true;
break;
}
}
if(!flag)
for(int i = 65;i <= 122;i ++)
if(v[i].size())
{
dfs(i);
break;
}
for(int i = num ; i >= 1; i--)
printf("%c",(char)ans[i]);
return 0;
}