题意:
给一些字符串,问是否可以把这些字符串连成一排,使前一个串的最后一个字符和后一个串的第一个字符一样。
分析:
把每个字符串都看成边就转化为有向图的欧拉路径(回路)问题了,这种O(e)的暴搜很巧妙。
代码:
//poj 2337
//sep9
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
const int maxN=30;
const int maxM=2024;
vector< pair<int,int> > adj[maxN];
vector<int> path;
int f[maxN];
bool vis[maxM];
string name[maxM];
int in[maxN],out[maxN];
void add(int x,int y,int z)
{++in[y];++out[x];adj[x].push_back(make_pair(z,y));
}int find(int u)
{return f[u]==u?u:f[u]=find(f[u]);
}int cmp(pair<int,int> a,pair<int,int> b)
{return strcmp(name[a.first].c_str(),name[b.first].c_str())<0;
}
void dfs(int u)
{int i;for(i=0;i<adj[u].size();++i){int e=adj[u][i].first;int v=adj[u][i].second;if(!vis[e]){vis[e]=true;dfs(v);path.push_back(e);}}
}bool solve()
{int i,j;for(i=0;i<26;++i) f[i]=i;for(i=0;i<26;++i)for(j=0;j<adj[i].size();++j){int u=i,v=adj[i][j].second;int pu=find(u),pv=find(v);if(pu!=pv)f[pu]=pv;}int origin=-1,end=-1,start=-1,p=-1;for(i=0;i<26;++i) if(in[i]>0||out[i]>0){if(origin==-1)origin=i;if(find(i)!=find(origin))return false;sort(adj[i].begin(),adj[i].end(),cmp);if(in[i]==out[i])continue;if(in[i]==out[i]+1&&end==-1){end=i;continue;}if(in[i]+1==out[i]&&start==-1){start=i;continue;}return false;}if(start==-1&&end==-1)p=origin;else if(start!=-1&&end!=-1)p=start;elsep=-1;if(p==-1)return false; path.clear();memset(vis,false,sizeof(vis));dfs(p);reverse(path.begin(),path.end());return true;
}int main()
{int i,j,x,y,z,cases,n;scanf("%d",&cases);while(cases--){scanf("%d",&n); for(i=0;i<26;++i)adj[i].clear();memset(out,0,sizeof(out));memset(in,0,sizeof(in));for(i=1;i<=n;++i){cin>>name[i];int len=name[i].length();int x=name[i][0]-'a';int y=name[i][len-1]-'a';add(x,y,i);}if(solve()==false)printf("***\n");else{cout<<name[path[0]];for(i=1;i<path.size();++i)cout<<"."<<name[path[i]];printf("\n");} }return 0;
}