题解 P1341 【无序字母对】

使用算法：[Hierholzer算法](https://en.wikipedia.org/wiki/Eulerian\_path#Hierholzer's\_algorithm)。 做法简单来说就是通过dfs结束时间戳来构造串。 实现细节详见代码。 ```cpp #include <cstdio> #define maxn 257 int G[maxn][maxn]; // 图 int deg[maxn]; // 度 char tmp[maxn]; char res[maxn * maxn]; // 结果 int n; void dfs(int i) { for(int j = 0; j < maxn; j++) { if(G[i][j]) { G[i][j] = G[j][i] = 0; // 删边 dfs(j); } } res[n--] = i; // 记录 } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%s", tmp); G[tmp[0]][tmp[1]] = G[tmp[1]][tmp[0]] = 1; deg[tmp[0]]++; deg[tmp[1]]++; } char fir = 0, cnt = 0; for(int i = 0; i < maxn; i++) { // 计算度数情况 if(deg[i] & 1) { cnt++; if(!fir) fir = i; } } if(!fir) for(int i = 0; i < maxn; i++) if(deg[i]) {fir = i; break;} if(cnt && cnt != 2) return puts("No Solution"), 0; // 判断无解 dfs(fir); puts(res); return 0; } ```