题目链接: poj 2337
题目大意: 给出N个单词,单词A的开头与另外单词B结尾相同
则单词A和单词B可以连起来,问是否可以把所有单词都串成一条线
输出最小字典序的(按单词的字典序串)
解题思路: 对于每个单词,把单词的起点和终点字母当作顶点
这个单词即是起点到终点的一条单向边
根据有向图的欧拉图判断,若顶点的出度-入度为0,或者一个为1一个为-1则是欧拉通路
根据题意还可能是不连通的图,所以最后在判断一下是否是联通图
PS:欧拉路径的问题要记得判断图是否联通
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #define MAX 2010 #define INF 0x3f3f3f using namespace std; int k,Index,visit[MAX],pre[50],In[50],To[50],ans[MAX]; struct snode{ int len; char ch[25]; }num[MAX]; struct node{ int to,next,w; }edge[MAX<<3]; void Add_edge(int a,int b,int w) { edge[Index].to=b; edge[Index].w=w; edge[Index].next=pre[a]; pre[a]=Index++; } bool cmp(struct snode a,struct snode b) { if(strcmp(a.ch,b.ch)>=0) return false; return true; } void Fleury(int start) { int i,v; for(i=pre[start];i!=-1;i=edge[i].next) { v=edge[i].to; if(!visit[edge[i].w]) { visit[edge[i].w]=1; Fleury(v); ans[++k]=edge[i].w; //记录边的访问顺序 } } } int main() { char ch1[25]; int t,i,j,n,m,a,b,pd,pd1,pd2,start; scanf("%d",&t); while(t--) { Index=pd1=pd2=k=0; memset(visit,0,sizeof(visit)); memset(pre,-1,sizeof(pre)); memset(num,0,sizeof(num)); memset(In,0,sizeof(In)); memset(To,0,sizeof(To)); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",num[i].ch); num[i].len=strlen(num[i].ch); } sort(num+1,num+1+n,cmp); start=INF; for(i=n;i>=1;i--) { a=num[i].ch[0]-'a'+1; b=num[i].ch[num[i].len-1]-'a'+1; Add_edge(a,b,i); To[a]++,In[b]++; if(start>a) start=a; if(start>b) start=b; } m=-1; for(i=1;i<=26;i++) { if(To[i]-In[i]==1) { if(m==-1) m=i; pd1++; } else if(To[i]-In[i]==-1) pd2++; else if(To[i]!=In[i]) { pd1=3; break; } } if(pd1==1&&pd2==1) //若出度-入度之差为1和-1的点各有一个,起点是值1的 start=m; else if(pd1==0&&pd2==0) //不存在则选序号最小的顶点 start=start; else { printf("***\n"); continue; } Fleury(start); if(k!=n) //判断图是否联通 { printf("***\n"); continue; } for(i=k;i>=1;i--) { printf("%s%c",num[ans[i]].ch,".\n"[i==1]); } } return 0; }