欧拉回路是指：在一个连通图$G$中，若存在一条回路使得$G$中的每条边都被且仅被经过一次，这条回路就叫欧拉回路，这个图就是欧拉图。

另外，在一个连通图$G$中，若存在一条路径使得$G$中的每条边都被且仅被经过一次，这条路径就叫欧拉通路，这个图就是半欧拉图。

很显然，如果统计所有点的度数$deg[i]$，对于一个欧拉图，不存在一个点$u$的入度$deg[u]$为奇数；对于一个半欧拉图，有且仅有两个点$u,v$的度数$deg[u],deg[v]$为奇数，且该图中的欧拉通路以$u,v$为端点。

$\textbf{Hierholzer}$算法

$Hierholzer$算法是指：在一个欧拉图$G$中，随机选取一个点作为起始点，每次遍历点$u$所连接的点$v$，对于点$v$，先删去无向边$<u,v>$，然后对点$v$跑$\text{dfs}$。循环结束后，将$u$倒序记录在$res[i]$数组中。算法结束后，$res[i]$中的路径就是一条欧拉回路。

下面是用邻接矩阵存图后的$Hierholzer$算法实现。

inline void dfs(int i) {
    for(register int j = 1; j <= MAXN; j++) {
        if(G[i][j]) {
            G[i][j] = G[j][i] = 0;
            dfs(j);
        }
    }
    res[tail--] = i;
}

例题 P1341

思路： 给出的字母对实际上就是在构造边，存完边之后直接跑$Hizerholzer$即可。由于要保证字典序最小，所以只需要注意在遍历的时候按照字典序从小到大遍历就可以了。

//code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)'z' + 10;

int G[MAXN][MAXN];
int deg[MAXN];
char res[MAXN * MAXN];
int n, tail;

inline void dfs(int i) {
    for(register int j = 'A'; j <= 'z'; j++) {
        if(G[i][j]) {
            G[i][j] = G[j][i] = 0;
            dfs(j);
        }
    }
    res[tail--] = (char)i;
}

int main() {
    scanf("%d", &n);
    tail = n;
    for(register int i = 1; i <= n; i++) {
        char s[10];
        scanf("%s", s);
        G[s[0]][s[1]] = G[s[1]][s[0]] = 1;
        deg[s[0]]++, deg[s[1]]++;
    }
    char begin = 0;
    int cnt = 0;
    for(register int i = 'A'; i <= 'z'; i++) {
        if(deg[i] % 2) {
            cnt++;
            if(!begin)
                begin = (char)i;
        }
    }
    if(cnt && cnt != 2) {
        printf("No Solution");
        return 0;
    }
    if(!begin)
        for(register int i = 'A'; i <= 'z'; i++)
            if(deg[i]) {
                begin = (char)i;
                break;
            }
    dfs(begin);
    puts(res);
    return 0;
}