整整一天都在弄这个 ,终于AC了 。
需要注意的地方都在代码注释里了!
#include<iostream> #include<cstdio> #include<string> #include<algorithm> using namespace std; #define EMAX 1030 int t,n; int num;//记录边数目 int vis[30]; int head[EMAX]; int next[EMAX]; int fa[30]; int in[30]; int out[30]; int stk[EMAX];//记录打印顺序 int top; string str[EMAX]; struct node { int u;//起点 int v;//终点 string s; int flag; }; node edge[EMAX]; int num1,num2; void init() { num=0; top=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); for(int i=0;i<30;i++) fa[i]=i; } //添加边的方法 void addnode(int u,int v,string s) { edge[num].u=u; edge[num].v=v; edge[num].s=s; edge[num].flag=0; next[num]=head[u]; head[u]=num++; } //find int find(int a) { if(a==fa[a]) return a; else return fa[a]=find(fa[a]); } bool cmp(string a,string b) { return a>b; //因为是用头插法建立节点 所有必须从大到小排序 } int iseuler() { // 第一个条件 int fnum=0; int i; for(i=1;i<=26;i++) if(vis[i]&&find(i)==i) fnum++; if(fnum>1) return 0; //第二个条件 num1=num2=0; for(i=1;i<=26;i++) if(vis[i]&&in[i]!=out[i]) { if(in[i]-out[i]==1) num1++; else if(out[i]-in[i]==1) num2++; else return 0; } if(num1==1&&num2==1) return 1; if(num1==0&&num2==0) return 1; return 0; } void dfs(int from) { for(int i=head[from];i!=-1;i=next[i]) { if(!edge[i].flag) { edge[i].flag=1; dfs(edge[i].v); stk[top++]=i; } } } int main() { //freopen("in.txt","r",stdin); scanf("%d",&t); while(t--) { int i; scanf("%d",&n); init();//初始化 for(i=0;i<n;i++) { // scanf("%s",str[i]); cin>>str[i]; } //排序 sort(str,str+n,cmp); for(i=0;i<n;i++) { int u=str[i][0]-'a'+1;//顶点从1到26 int v=str[i][(str[i].length())-1]-'a'+1; vis[u]=1; vis[v]=1; out[u]++; in[v]++; if(find(u)!=find(v)) fa[find(v)]=find(u); addnode(u,v,str[i]);//边从0到num } if(iseuler()) { int start;//起点的选择:如果是欧拉通路 则选择出度比入度大一的那个点, //否则选字典序最小的那个点!! 这点很重要! //选择入口 if(num1==1&&num2==1) { for(int k=0;k<num;k++) { if(out[edge[k].u]-in[edge[k].u]==1) { start=k; break; } } } else { start=num-1;//选字典序最小的那个dian } dfs(edge[start].u); for(i=num-1;i>0;i--) cout<<edge[stk[i]].s<<"."; cout<<edge[stk[i]].s<<endl; } else { printf("***\n"); } } return 0; }
因为该题要按字典序输出,我就再这里WA了好久 ,,一开始我是将各个字符串从小到大排序,而我采用的是头插法建立节点。这样同一起点的单词 不一定会按照从小到大的排序的。 如ab aba 。所以应该从大到小排序。
还有一点要注意的是
选择起点:如果是欧拉通路选择出度比入度大一的点,如果是回路,则选择字典序最小的那个点,以它为入口
相关推荐
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
三道几何题:hdu 1007、hdu 2289、poj 3714
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
北京大学online judge题号3601,解答及其实验报告
经典的状态DP难题,非常好的的题目,我做了很久才做出来,强烈推荐!!1
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
POJ1048,加强版的约瑟夫问题 难度中等
POJ14_MONI2.zip
Catenyms poj hoj 欧拉回路输出路径
poj两道题的c++实现。已经测试过可以通过oj
O(nlogn)凸包问题 poj2187
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
POJ1753 Flip Game题目完整代码及报告
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
详细解释 ,既有源代码又有书面文字解释,ppt,在VC6上完成
poj2516代码最小费用最大流
Time Limit: 1000ms Memory limit: 65536kB 题目描述 有9个时钟,排成一个3*3的矩阵。 现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示,每个移动会将若干个时钟的...