题目：https://www.luogu.org/problemnew/show/P1341
题意：给定n对字母对，要求构造一个个数为n+1的字符串，使得每一个字母对都在里面出现过。
思路：这种题目都卡了好久，代码能力真的不行了啊。
其实就是每个字母是节点，每个字母对就是这两个字母之间连一条边，每个字母对都要出现就是每条边都要经过一次且只经过一次。
所以就是一个欧拉路的问题。
欧拉路问题很简单，首先如果度数是奇数的点只能是0或2个。
之后就是遍历节点的每一条边，全部dfs结束了之后把这个节点加入栈中就行了。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair<int, int> pr; 17 18 int n; 19 const int maxm = 3000; 20 const int maxn = 300; 21 int g[maxn][maxn]; 22 //int head[maxn], to[maxm * 2], nxt[maxm * 2], vis[maxm * 2]; 23 int deg[maxn]; 24 int tot = 1; 25 26 stack<int>ans; 27 28 void dfs(int now){ 29 30 for(int i = 0; i <= 150; i++){ 31 if(g[now][i] <= 0)continue; 32 g[now][i]--;g[i][now]--; 33 dfs(i); 34 } 35 ans.push(now); 36 //printf("%c", now); 37 } 38 39 int main() 40 { 41 scanf("%d", &n); 42 for(int i = 0; i < n; i++){ 43 string s; 44 cin>>s; 45 g[s[0]][s[1]]++;g[s[1]][s[0]]++; 46 //cout<<s[0]-'A'<<" "<<s[1]-'A'<<endl; 47 deg[s[0]]++; 48 deg[s[1]]++; 49 //add(s[0] - 'A', s[1] - 'A'); 50 } 51 52 //printf("%d ", deg['I' - 'A']); 53 int cnt = 0, dian = 0; 54 for(int i = 0; i <= 150; i++){ 55 if(deg[i] % 2){ 56 cnt++; 57 if(!dian)dian = i; 58 } 59 } 60 if(!cnt){ 61 for(int i = 0; i <= 150; i++){ 62 if(deg[i]){ 63 dian = i; 64 break; 65 } 66 } 67 } 68 69 if(cnt && cnt != 2){ 70 printf("No Solution "); 71 } 72 else{ 73 dfs(dian); 74 //cout<<ans.size()<<endl; 75 if(ans.size() >= n+1){ 76 while(!ans.empty()){ 77 printf("%c", ans.top()); 78 ans.pop(); 79 } 80 printf(" "); 81 } 82 else{ 83 printf("No Solution "); 84 } 85 } 86 87 }