[Luogu1341]无序字母对(欧拉回路)
2024-10-17 01:49:56
按题意给定字符串建无向图,找欧拉回路
按照定义,当没有奇数度点或者只有2个奇数度点时才有欧拉回路
Code
#include <cstdio>
#include <algorithm>
#define N 666
using namespace std; int n,g[N][N],cnt,in[N],st,path[N]; inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} int f(char ch){
if(ch>='a'&&ch<='z') return ch-'a'+27;
else return ch-'A'+1;
} void dfs(int i){
for(int j=1;j<=52;++j)//字典序最小
if(g[i][j]){
g[i][j]=g[j][i]=0;
dfs(j);
}
path[++cnt]=i;
} int main(){
n=read();
for(int i=1;i<=n;++i){
char s[10];
scanf("%s\n",s);
int u=f(s[0]),v=f(s[1]);
++in[u],++in[v];
g[u][v]=g[v][u]=1;
}
for(int i=52;i>=1;--i) if(in[i]&1) cnt++,st=i;
if(cnt!=0&&cnt!=2){
printf("No Solution\n");
return 0;
}
if(!cnt) for(int i=1;i<=52;++i) if(in[i]){st=i;break;}//字典序最小
cnt=0;
dfs(st);
for(int i=cnt;i>=1;--i) printf("%c",(path[i]<=26)?'A'+path[i]-1:'a'+path[i]-27);
return 0;
}
最新文章
- hibernate多对多关联映射
- 在windows上如何安装python web引擎jinja2
- Caliburn.Micro学习笔记目录——li-peng
- oracle 知识
- ACM: 强化训练-Beautiful People-最长递增子序列变形-DP
- osg渲染数据高程文件
- linux(以ubuntu为例)下Android利用ant自动编译、修改配置文件、批量多渠道,打包生成apk文件
- 分布式文件系统FastDFS原理介绍
- 静态变量符 static
- Codeforces 219D Choosing Capital for Treeland
- 开始学习.net的第二天
- bzoj usaco 金组水题题解(2)
- ADT Android开发环境搭建小记
- Linux学习笔记:【000】Linux系统入门
- python 2 字典的基本使用
- C#连接MySQL 操作步骤
- 【【模板】严格次小生成树[BJWC2010]】
- django 模板语言之 simple_tag 自定义模板
- Openresty配置文件上传下载
- javaScript Promise 入门