首页 > 代码库 > UESTC 917 方老师的分身IV --求欧拉路径
UESTC 917 方老师的分身IV --求欧拉路径
判断欧拉路径是否存在及求出字典序最小的欧拉路径问题（如果存在）。
将字符串的第一个字母和最后一个字母间连边，将字母看成点，最多可能有26个点（a-z），如果有欧拉路径，还要判断是否有欧拉回路，如果有，则需要找一个字典序最小的点开始生成这条链，否则以起点开始生成链，起点即为出度比入度大1的点。
欧拉路径是否存在的判定：
1.全部点在一个联通块 ----用并查集判联通块的数量
2.所有点出度入度相等 ----in[],out[]记录出度与入度
3.或者有一个出度比入度小1，另一个出度比入度大1（源点与汇点）
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#define Mod 1000000007using namespace std;#define N 2007string ss[N];struct node{ int u,v,next; string w;}G[N];int first[28],fa[28],in[28],out[28],vis[28];int tot,k,start;int evis[N];string ans[N];void init(){ int i; for(i=0;i<28;i++) fa[i] = i; tot = 1; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(i=0;i<=2000;i++) { G[i].u = G[i].v = G[i].next = 0; G[i].w = ""; } memset(first,-1,sizeof(first)); memset(vis,0,sizeof(vis)); memset(evis,0,sizeof(evis)); for(int j=0;j<=2000;j++) ans[j] = "";}int findset(int x){ if(x != fa[x]) fa[x] = findset(fa[x]); return fa[x];}int cmp(string ka,string kb){ return ka>kb;}void addedge(int u,int v,string w){ G[tot].u = u; G[tot].v = v; G[tot].w = w; G[tot].next = first[u]; first[u] = tot++; out[u]++; in[v]++; vis[u] = vis[v] = 1; int fx = findset(u); int fy = findset(v); if(fx != fy) fa[fx] = fy;}int Euler_Path(){ int block = 0,i; int O = 0; int I = 0; start = -1; for(i=0;i<26;i++) { if(vis[i]) //涉及到的字母 { int fk = findset(i); if(fk == i) block++; if(block > 1) return false; if(in[i] == out[i]+1) //入大出，奇度数点 I++; else if(in[i]+1 == out[i]) //出大入，奇度数点 O++,start = i; else if(in[i] != out[i]) return false; } } if(block != 1) return false; if((O == I && O == 1) || (O == I && O == 0)) //没有奇度数点或者只有源点和汇点是奇度数点 { if(start == -1) //没有找到起点，是欧拉回路 { for(i=0;i<26;i++) { if(vis[i] && out[i] > 0) //找字典序最小的字母做起点 { start = i; return true; } } } //如果已找到起点,则不能是欧拉回路 if(O == I && O == 1) return true; return false; } return false;}void dfs(int v,int flag){ for(int e=first[v];e!=-1;e=G[e].next) { if(!evis[e]) //边没被访问 { evis[e] = 1; dfs(G[e].v,e); } } if(flag != -1) ans[k++] = G[flag].w;}int main(){ int t,i,j,n; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(i=1;i<=n;i++) cin>>ss[i]; sort(ss+1,ss+n+1,cmp); //qsort(ss+1,n,28,cmp); for(i=1;i<=n;i++) { int u = ss[i][0]-‘a‘; int v = ss[i][ss[i].length()-1]-‘a‘; addedge(u,v,ss[i]); } if(Euler_Path()) { k = 0; dfs(start,-1); cout<<ans[k-1]; for(i=k-2;i>=0;i--) cout<<"."<<ans[i]; printf("\n"); } else puts("***"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。