首页 > 代码库 > poj2337欧拉回路
poj2337欧拉回路
对字符串从小到大排序,邻接表正向插入。
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;const int maxn=2222;int cmp(const string &a,const string &b){ return a<b;}struct Node{ int to;int val;int vis;};string str[maxn];vector<Node> head[maxn];int vis[maxn];int father[100];void add(int from,int to,int val,int vis ){ Node k; k.to=to; k.val=val;k.vis=vis; head[from].push_back(k);}int getfather(int x){ if(x!=father[x]) father[x]=getfather(father[x]); return father[x];}void link(int a,int b){ int fa=getfather(a);int fb=getfather(b); father[fa]=fb;}stack<string > q;void dfs(int x){ int len=head[x].size(); for(int i=0;i<len;i++){ if(!head[x][i].vis){ //cout<<x<<" "<<head[x][i].to<<endl; head[x][i].vis=1; dfs(head[x][i].to); q.push(str[head[x][i].val]); } }}void output(){ string a= q.top(); q.pop(); cout<<a; while(!q.empty()){ cout<<"."<<q.top(); q.pop(); }}int in[100];int out[100];int main(){ int Icase; cin>>Icase; int n; while(Icase--){ memset(vis,0,sizeof(vis)); for(int i=0;i<26;i++) father[i]=i; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=0;i<=maxn;i++) head[i].clear(); cin>>n; for(int i=0;i<n;i++) cin>>str[i]; sort(str,str+n,cmp); for(int i=0;i<n;i++){ int a=str[i][0]-‘a‘; int len=str[i].size();int b=str[i][len-1]-‘a‘; add(a,b,i,0); vis[a]=1;vis[b]=1; in[b]++;out[a]++; link(a,b); } int ans=0; for(int i=0;i<26;i++) if(vis[i]) if(i==father[i]) ans++; int flag=0;int in1=0;int out1=0;int sign;int sign1; for(int i=0;i<26;i++) if(vis[i]) { sign1=i;break; } for(int i=0;i<26;i++) if(vis[i]){ if(in[i]==out[i]) continue; if(in[i]-out[i]==1){ in1++; } if(out[i]-in[i]==1){ out1++; sign=i; } if(out[i]-in[i]>1||out[i]-in[i]>1){ flag=1;break; } } //cout<<sign<<endl;system("pause"); if(!flag) if(in1>1||out1>1) flag=1; if(ans!=1||flag) cout<<"***"<<endl; else{ if(in1!=0) dfs(sign); else dfs(sign1); output(); cout<<endl; } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。