題意：
如果給出的單詞能夠首尾相接，請(qǐng)按字典序輸出單詞，中間要加’.’
否則輸出三個(gè)”*”.
思路：
歐拉回路
記得按字典序排序哦~
加邊的時(shí)候要倒著加。（鄰接表遍歷的時(shí)候是反著的）

記得清空vis數(shù)組（因?yàn)檫@個(gè)無(wú)腦錯(cuò)誤WA了好長(zhǎng)時(shí)間。。。。。）

隨便搞搞 就能過(guò)了。 數(shù)據(jù)不是很強(qiáng)…

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[1005][25]; int first[60],next[1005],tot,top,v[1005]; int cases,n,ansx,ansy,ansz,in[26],out[26],ans[1005]; bool vis[1005],flag,VIS[26]; struct node{char str[25];int length;}edge[1005]; void add(int x,int y,int z){v[z]=y;next[z]=first[x];first[x]=z;} bool cmp(node x,node y){return strcmp(x.str,y.str)>0?0:1;} void dfs(int x){for(int i=first[x];~i;i=next[i])if(!vis[i]){VIS[v[i]]=1;vis[i]=1,dfs(v[i]);ans[++top]=i;} } int main(){scanf("%d",&cases);while(cases--){memset(first,-1,sizeof(first));memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(vis,0,sizeof(vis));memset(VIS,0,sizeof(VIS));flag=ansx=ansy=ansz=top=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",edge[i].str);edge[i].length=strlen(edge[i].str);out[edge[i].str[0]-'a']++;in[edge[i].str[edge[i].length-1]-'a']++;}sort(edge+1,edge+1+n,cmp);for(int i=n;i;i--)add(edge[i].str[0]-'a',edge[i].str[edge[i].length-1]-'a',i);for(int i=0;i<=25;i++){if(in[i]-out[i]==1)ansx++;else if(out[i]-in[i]==1)ansy++;else if(in[i]!=out[i])ansz++;}if(!ansz&&ansx==ansy&&(ansx==0||ansx==1)){int jy;if(ansx==1){for(int i=0;i<26;i++)if(out[i]-in[i]==1){jy=i;break;}}else{for(int i=0;i<26;i++)if(out[i]){jy=i;break;}}VIS[jy]=1;dfs(jy);for(int i=0;i<=25;i++)if((in[i]||out[i])&&!VIS[i])flag=1;}else flag=1;if(!flag){for(int i=top;i>=2;i--)printf("%s.",edge[ans[i]].str);printf("%s\n",edge[ans[1]].str);}else puts("***");} }

轉(zhuǎn)載于:https://www.cnblogs.com/SiriusRen/p/6532393.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的POJ 2337 欧拉回路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。