今日题目：字母
题目分析
题目难度：⭐️⭐️⭐️
题目涉及算法：欧拉回路，dfs。
ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力
题解报告：
1.思路
我用的Hierholzer算法，用dfs构造串
1.选择任一顶点为起点，遍历所有相邻边。
2.深度搜索，访问相邻顶点。将经过的边都删除。
3.如果当前顶点没有相邻边，则将顶点入栈。
4.栈中的顶点倒序输出，就是从起点出发的欧拉回路。
各位感兴趣可以去看看搜一下
2.代码
#include<bits/stdc++.h> using namespace std; const int N = 1000; int t[N][N],d[N]; char s[N],arr[N*N]; int n; void dfs(int i) { for(int j=0;j<N;j++) { if(t[i][j]) { t[i][j] = 0; t[j][i] = 0; dfs(j); } } arr[n--] = i; } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>s; t[s[0]][s[1]] = 1; t[s[1]][s[0]] = 1; d[s[0]]++; d[s[1]]++; } char sum = 0, num = 0; for(int i=0;i<N;i++) { if(d[i]&1) { num++; if(!sum) { sum = i; } } } if(!sum) { for(int i=0;i<N;i++) { if(d[i]) { sum = i; break; } } } if(num&&num!=2) { cout<<"No Solution"; return 0; } dfs(sum); puts(arr); return 0; }
