P1341 无序字母对

提交 24.87k

通过 6.80k

时间限制 1.00s

内存限制 125.00MB

题目提供者 yeszy

难度提高+/省选-

历史分数100

提交记录

查看题解

题目描述

给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入格式

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式

输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

输入输出样例

输入 #1

4

aZ

tZ

Xt

aX

输出 #1

XaZtX

说明/提示

【数据规模与约定】

不同的无序字母对个数有限，n的规模可以通过计算得到。

思路

　　把字母相连看作连边，对整张图来说，每个字母对出现 = 可以找到一个欧拉路径/回路，所以只要先判断图是否连通，即判断是否该点：其度不为0且祖先是它本身。

　　对于一张连通图来说，只要判断它是否能形成欧拉路径/回路即可，也就是有且只有两个度为奇数的点或全部的点度为偶数。

　　如果可以形成欧拉路径/回路，就找一个度不为0的点作为起点套Hierholzer算法模板；

　　Hierholzer算法存答案时需要反向存，这样做的好处是保证了无路可走时存下来的答案一定是欧拉路径的终点。

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 207;
 47 
 48 int n;
 49 
 50 int edge[maxn][maxn];
 51 int deg[maxn], fa[maxn];//出入度
 52 char ans[maxn*maxn];
 53 
 54 stack <char> s;
 55 
 56 int fid(int x) {
 57     return x == fa[x] ? x : fid(fa[x]);
 58 }
 59 
 60 void init() {
 61     for (int i = 64; i <= 128; ++i) {
 62         fa[i] = i;
 63     }
 64 }
 65 
 66 void dfs(int x) {
 67     for (int i = 64; i <= 128; ++i) {
 68         if(edge[x][i]) {
 69             edge[x][i] = edge[i][x] = 0;
 70             dfs(i);
 71         }
 72     }
 73     ans[n--] = x;
 74 }
 75 
 76 int main()
 77 {
 78     cin >> n;
 79     char a[5];
 80     int cnt = 0;
 81     init();
 82     for(int i = 1; i <= n; i++) {
 83         cin >> a;
 84         edge[a[0]][a[1]] = edge[a[1]][a[0]]=1;
 85         deg[a[0]]++;
 86         deg[a[1]]++;
 87         int x = fid(a[0]), y = fid(a[1]);
 88         fa[x]=y;
 89         //printf("x:fa[%d]:%d deg[%d]:%d\n",xx,fa[xx],a[0],deg[a[0]]);
 90         //printf("y:fa[%d]:%d deg[%d]:%d\n",yy,fa[yy],a[1],deg[a[1]]);
 91     }
 92     
 93     for (int i = 64; i <= 128; ++i) {
 94         
 95         if(fa[i] == i && deg[i]) {
 96             cnt++;
 97             //dbg(cnt);
 98         }
 99     }
100     //dbg(cnt);
101     if(cnt != 1) {//图不连通
102         puts("No Solution");
103         return 0;
104     }
105     //dbg(cnt);
106     cnt = 0;
107     int head = 0;
108     for (int i = 64; i <= 128; ++i) {
109         if(deg[i] & 1) {
110             cnt++;
111             if(!head)
112                 head = i;
113             //dbg(cnt);
114         }
115     }
116     if(cnt && cnt != 2) {
117         puts("No Solution");
118         return 0;
119     }
120     if(!head) {
121         for (int i = 64; i <= 128; ++i) {
122             if(deg[i]) {
123                 head = i;
124                 break;
125             }
126         }
127     }
128     dfs(head);
129     cout << ans << endl;
130     return 0;
131 }

View Code

P1341 无序字母对【欧拉路径】- Hierholzer模板