洛谷P1341 无序字母对

题目链接：https://www.luogu.org/problem/P1341

思路：

给2n个点，取出其中n+1个点，判断能不能组成一个符合题意的字符串。

可以比拟图，n + 1个点有n条边，然后他们又是一条路上的点。

可以比拟欧拉图，如果可以构成环，就是说每个点的度都是偶数，

即从任意点出发都能回到该点，就是欧拉闭迹，即欧拉回路。

如果不能构成环，有两个点的度是奇数，其他点的度数都是偶数，说明

可以组成一条欧拉开迹，就是欧拉回路拆去了某条边，让环无法形成。

那题目就简单了，这里有一个注意点，也算一个坑吧，就是输出路线时，

如果你是边输出边遍历点的话会出现一种情况：

ax xy yz za zz

输出答案： axyzaz

实际答案： axyzza

为什么呢，第一个答案很容易想到，第二个呢？

注意：我们在存答案时，我们总是 str[++l] = ic[now]（代码里有），那么什么时候才会写下第一个答案呢？

显然，当一个分支到底了，写下答案并层层回归。那么我们就不难想出第二种答案了，

当z因为贪心遍历到a，而a没有与其他点相邻，那么a就是第一个写下的答案了，如果还有与a相邻的点，

那么一定会进入另一个分支。

补：当然需要判是否连通，但这个题不判也可以过，数据有点水。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <map>
  7 #include <cmath>
  8 #include <iomanip>
  9 using namespace std;
 10 
 11 typedef long long LL;
 12 #define inf (1LL << 25)
 13 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 14 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
 15 #define per(i,j,k) for(int i = (j); i >= (k); i--)
 16 #define per__(i,j,k) for(int i = (j); i > (k); i--)
 17 
 18 const int N = 60;
 19 int tot[N];
 20 bool app[N];
 21 int fa[N];
 22 map<int,char> ic;
 23 map<char,int> ci;
 24 int G[N][N];
 25 char str[10010];
 26 int l;
 27 
 28 int find_root(int x){
 29     return fa[x] == x ? x : find_root(fa[x]);
 30 }
 31 
 32 void merge(int x,int y){
 33     int fax = find_root(x);
 34     int fay = find_root(y);
 35     fa[fax] = fay;
 36 }
 37 
 38 void dfs(int now){
 39 
 40     rep(i,1,52) if(app[i] && G[now][i]){
 41         G[now][i]--;
 42         G[i][now]--;
 43         dfs(i);
 44     }
 45     str[++l] = ic[now];
 46 }
 47 
 48 int main(){
 49 
 50     ios::sync_with_stdio(false);
 51 
 52     cin.tie(0);
 53 
 54 
 55     rep(i,1,52) fa[i] = i;
 56     //编号
 57     rep(i,0,25){
 58         ci[(char)'A' + i] = i + 1;
 59         ic[i + 1] = (char)'A' + i;
 60     }
 61     rep(i,26,51){
 62         ci[(char)'a' + i - 26] = i + 1;
 63         ic[i + 1] = (char)'a' + i - 26;
 64     }
 65 
 66     //  rep(i,1,52) cout << ic[i] << " ";
 67     //  cout << endl;
 68 
 69     int n;
 70     cin >> n;
 71     char a,b;
 72     rep(i,1,n){
 73         
 74         cin >> a >> b;
 75 
 76         int ia = ci[a];
 77         int ib = ci[b];
 78         G[ia][ib]++; G[ib][ia]++;
 79         app[ia] = true; app[ib] = true;
 80         tot[ia]++; tot[ib]++;
 81         merge(ia,ib);
 82     }
 83 
 84     int odd = 0; //奇数度
 85     int even = 0; //偶数度
 86     rep(i,1,52) if( app[i]){
 87         if(tot[i] & 1) odd++;
 88         else even++;
 89     }
 90 
 91     //判连通
 92     int t = 0;
 93     rep(i,1,52) if(fa[i] == i && app[i]) {
 94         t++;
 95         if(t == 2) break;
 96     }
 97     
 98     //不连通
 99     if(t == 2) cout << "No Solution" << endl; 
100     else if(odd == 2){ //欧拉回路
101         rep(i,1,52) if(tot[i] & 1) {
102             dfs(i);
103             break;
104         }
105 
106         per(i,l,1) cout << str[i];
107         cout << endl;
108     }
109     else if(odd == 0){ //欧拉开迹
110         rep(i,1,52) if(app[i]){
111             dfs(i);
112             break;
113         }
114         per(i,l,1) cout << str[i];
115         cout << endl;
116     }
117     else cout << "No Solution" << endl;
118 
119 
120     getchar(); getchar();
121     return 0;
122 }