題目鏈接: poj 2337
題目大意: 給出N個單詞,單詞A的開頭與另外單詞B結尾相同
則單詞A和單詞B可以連起來,問是否可以把所有單詞都串成一條線
輸出最小字典序的(按單詞的字典序串)
解題思路: 對於每個單詞,把單詞的起點和終點字母當作頂點
這個單詞即是起點到終點的一條單向邊
根據有向圖的歐拉圖判斷,若頂點的出度-入度為0,或者一個為1一個為-1則是歐拉通路
根據題意還可能是不連通的圖,所以最後在判斷一下是否是聯通圖
PS:歐拉路徑的問題要記得判斷圖是否聯通
代碼:
#include#include #include #include #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; }