南阳理工OJ 99 单词拼接（欧拉通路）
#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<vector>#include<queue>using namespace std;const int maxcolor=26;int G[maxcolor+1][maxcolor+1];vector<string> ans;//存放结果数组priority_queue<string, vector<string>, greater<string> >mm[maxcolor+1][maxcolor+1];//按字典序排int abs(int x){ return x>0?x:-x;}void euler(int u){ int uu,vv,flag=1; while(flag) { string str="{";//初始化str为最大 flag=0; for(int v=1;v<=maxcolor;v++)//找其中字典序最小的 { if(G[u][v]) { flag=1; if(str>mm[u][v].top()) { str=mm[u][v].top(); uu=u; vv=v; } } } if(flag)//继续深搜字典序最小的 { mm[uu][vv].pop(); G[uu][vv]--; euler(vv); ans.push_back(str);//最小的存在结果数组里面 } }}int f()//找起点函数{ int ru,chu,res=0,start=0; for(int i=1;i<=maxcolor;i++) { ru=chu=0; for(int j=1;j<=maxcolor;j++) { if(start==0&&G[i][j]!=0)start=i;//如果是欧拉图，起点就是第一个字母最小的那个单词 chu+=G[i][j]; ru+=G[j][i]; } res+=abs(chu-ru); if(chu>ru)start=i;//如果是半欧拉图，起点就是出度大一点的那个单词 } if(res>2)return -1;//如果不构成欧拉路，就跳出 return start;}int main(){// freopen("Input.txt","r",stdin); int T,start; string str,term; scanf("%d",&T); while(T--) { memset(G,0,sizeof(G)); int n; scanf("%d",&n); for(int i=1;i<=26;i++) for(int j=1;j<=26;j++) while(!mm[i][j].empty())mm[i][j].pop(); for(int i=0;i<n;i++) { cin>>str; int len=(int)str.size(); G[str[0]-'a'+1][str[len-1]-'a'+1]++;//存图，单词的开始为出度点，结尾为入度点 mm[str[0]-'a'+1][str[len-1]-'a'+1].push(str); } start=f(); if(start==-1) { printf("***\n"); continue; } ans.clear(); euler(start); if((int)ans.size()!=n)//如果单词没有找完，说明不连通，就输出*** { printf("***\n"); continue; } for(int i=ans.size()-1;i>=0;i--)//输出结果 { if(i!=0)cout<<ans[i]<<"."; else cout<<ans[i]; } cout<<endl; } return 0;}
?
?
?
?
?
?
?
