洛谷P1341 无序字母对【欧拉路】【dfs】

题目https://www.luogu.org/problemnew/show/P1341

题意:给定n对字母对,要求构造一个个数为n+1的字符串,使得每一个字母对都在里面出现过。

思路:这种题目都卡了好久,代码能力真的不行了啊。

其实就是每个字母是节点,每个字母对就是这两个字母之间连一条边,每个字母对都要出现就是每条边都要经过一次且只经过一次。

所以就是一个欧拉路的问题。

欧拉路问题很简单,首先如果度数是奇数的点只能是0或2个。

之后就是遍历节点的每一条边,全部dfs结束了之后把这个节点加入栈中就行了。

 #include<cstdio>
#include<cstdlib>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<iostream> #define inf 0x7fffffff
using namespace std;
typedef long long LL;
typedef pair<int, int> pr; int n;
const int maxm = ;
const int maxn = ;
int g[maxn][maxn];
//int head[maxn], to[maxm * 2], nxt[maxm * 2], vis[maxm * 2];
int deg[maxn];
int tot = ; stack<int>ans; void dfs(int now){ for(int i = ; i <= ; i++){
if(g[now][i] <= )continue;
g[now][i]--;g[i][now]--;
dfs(i);
}
ans.push(now);
//printf("%c", now);
} int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++){
string s;
cin>>s;
g[s[]][s[]]++;g[s[]][s[]]++;
//cout<<s[0]-'A'<<" "<<s[1]-'A'<<endl;
deg[s[]]++;
deg[s[]]++;
//add(s[0] - 'A', s[1] - 'A');
} //printf("%d\n", deg['I' - 'A']);
int cnt = , dian = ;
for(int i = ; i <= ; i++){
if(deg[i] % ){
cnt++;
if(!dian)dian = i;
}
}
if(!cnt){
for(int i = ; i <= ; i++){
if(deg[i]){
dian = i;
break;
}
}
} if(cnt && cnt != ){
printf("No Solution\n");
}
else{
dfs(dian);
//cout<<ans.size()<<endl;
if(ans.size() >= n+){
while(!ans.empty()){
printf("%c", ans.top());
ans.pop();
}
printf("\n");
}
else{
printf("No Solution\n");
}
} }
上一篇:洛谷 P1341 无序字母对(欧拉回路)


下一篇:java集合框架list和set