洛谷P1341 无序字母对

题面

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

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

分析

各不相同的无序字母对总数有限，有52*51/2=1326种，这是n的规模。

此题的建模是图论，给出的无序字母对相当于图的边，图的顶点上是字母，这样构造出来n+1长度的字符串就必然要包含所有边（而一个顶点可以经过多次），简单判断后这是寻找图的欧拉通路/回路问题。

欧拉通路：包含图上所有的边但不首尾相连
欧拉回路：包含图上所有边且首尾相连

用dfs即可找出欧拉路，对边记录vis即可，如果找到了尽头，但是仍然有边未被选中，则回溯

代码

#include "cstdlib"
#include 
#include 
#include 
#include
#include 
#include
#include
using namespace std;
vector<int>Edge[60];//存边,Edge[i]下包含从i出发的所有边,i编号：A1,B2...Z26,a27...z52
int vis[60][60];//记录边是否被用过,vis[j][i]表示这条边已经被用
int in[60];//记录连接边数，为了判断solution
int used = 0;//表示已经选中used条边
int n;//总边数
char ans[2000];
int ptr = 0;
int flag = 0;//已经找到解
char num_to_char(int num)//将1~52的数字转成对应的字母
{if (num <= 26)return num + 'A'-1;else return num-27 + 'a';
}
void dfs(int s)
{if (used == n) {flag = 1;return; }int t;//表示下一个顶点for (int i = 0; i < Edge[s].size(); i++)//按字典序，能保证较小{t = Edge[s][i];if (vis[s][t])continue;used++;vis[s][t] = 1, vis[t][s] = 1;ans[ptr++] = num_to_char(t);dfs(t);if (flag)return;used--;vis[s][t] = 0, vis[t][s] = 0;ptr--;}
}
int main()
{ios::sync_with_stdio(false);int u,v;string str;cin >> n;for (int i = 0; i < n; i++){cin >> str;if (str[0] <= 'Z')u = str[0] - 'A'+1;else u = str[0] - 'a'+27;if (str[1] <= 'Z')v = str[1] - 'A'+1;else v = str[1] - 'a'+27;Edge[u].push_back(v);Edge[v].push_back(u);in[v]++;in[u]++;}int cnt = 0;//度为奇数点的个数for (int i = 1; i <= 52; i++){if (in[i] % 2 == 1) { cnt++; v = u;u = i; }sort(Edge[i].begin(), Edge[i].end());}if (cnt == 0) {//欧拉回路情况，起点任意for (int i = 1; i <= 52; i++){if (Edge[i].size() > 0) { ans[ptr++] = num_to_char(i);dfs(i); break; }//从第一位开始保证字典序小}cout << ans;}else if(cnt==2)//欧拉通路情况{ans[ptr++] = num_to_char(min(u, v));dfs(min(u, v));cout << ans;}else {cout << "No Solution";}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！