首页 > 代码库 > POJ 2337 Catenyms
POJ 2337 Catenyms
http://poj.org/problem?id=2337
题意：
判断给出的单词能否首尾相连，输出字典序最小的欧拉路径。
思路：
因为要按字典序大小输出路径，所以先将字符串排序，这样加边的时候就会优先加字典序小的边，dfs的时候也就会先走字典序小的边。
判断一下图的连通性以及是否存在欧拉道路。
然后进行深搜寻找欧拉路径，因为欧拉路径时要逆序输出的，所以这里需要先保存起来，最后再次逆序输出即可得到正确的路径。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef long long ull; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const int maxn = 1000 + 5; 18 19 struct Edge 20 { 21 int ID; 22 int v; 23 int vis; 24 Edge(){} 25 Edge(int id,int x,int y):ID(id),v(x),vis(y){} 26 }; 27 28 int n; 29 int p[30]; 30 int in[30], out[30]; 31 string str[maxn]; 32 33 vector<Edge> G[maxn]; 34 35 stack<int> sta; 36 37 int Find(int x) 38 { 39 return p[x]==x?x:p[x]=Find(p[x]); 40 } 41 42 void Fleury(int u) 43 { 44 for(int i=0;i<G[u].size();i++) 45 { 46 if(!G[u][i].vis) 47 { 48 G[u][i].vis=1; 49 Fleury(G[u][i].v); 50 sta.push(G[u][i].ID); //这儿是逆序存储 51 } 52 } 53 } 54 55 int main() 56 { 57 //freopen("in.txt","r",stdin); 58 int T; 59 scanf("%d",&T); 60 while(T--) 61 { 62 memset(in,0,sizeof(in)); 63 memset(out,0,sizeof(out)); 64 65 scanf("%d",&n); 66 for(int i=0;i<26;i++) {G[i].clear();p[i]=i;} 67 68 for(int i=0;i<n;i++) cin>>str[i]; 69 sort(str,str+n); //排序，按照字典序顺序加边，这样等下dfs的时候就会先选择字典序小的边 70 71 int start; 72 for(int i=0;i<n;i++) 73 { 74 int a=str[i][0]-‘a‘; 75 int b=str[i][str[i].size()-1]-‘a‘; 76 out[a]++; 77 in[b]++; 78 int x=Find(a); 79 int y=Find(b); 80 if(x!=y) p[x]=y; 81 G[a].push_back(Edge(i,b,0)); 82 if(i==0) start=a; 83 } 84 85 int cnt=0; 86 int num1=0,num2=0,num3=0; 87 for(int i=0;i<26;i++) 88 { 89 if((in[i]||out[i]) && p[i]==i) cnt++; 90 if(in[i]!=out[i]) 91 { 92 if(out[i]-in[i]==1) {start=i;num1++;} 93 else if(out[i]-in[i]==-1) num2++; 94 else num3++; 95 } 96 } 97 98 if(!num3 && ((num1==0 && num2==0) || (num1==1 && num2==1)) && cnt==1) 99 {100 Fleury(start);101 cout<<str[sta.top()]; sta.pop();102 while(!sta.empty())103 {104 cout<<"."<<str[sta.top()];105 sta.pop();106 }107 cout<<endl;108 }109 else {puts("***");continue;}110 }111 }
POJ 2337 Catenyms
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。