[POJ2337]Catenyms

题目大意：
　　定义一个catenym是一对单词，满足第一个单词的末尾字符与第二个单词的开头字符相等。
　　定义复合catenym是一些单词，满足第i个单词的末尾字符与第i+1个单词的开头字符相等。
　　给你n个字符串，判断它们是否能构成复合catenym。
　　如果能，求出字典序最小的那个catenym。

思路：
　　以字母为点，单词为边建图。用类似Fleury算法，跑一边欧拉路径，如果能跑出欧拉路经则说明可以构成。
　　为了保证catenym的字典序最小，我们就要保证在Fleury的时候，按照字典序遍历。
　　因此我们要先对所有的单词按字典序排序，然后加边。

 */

 #include<stack>

 #include<string>

 #include<vector>

 #include<iostream>

 #include<algorithm>

 #include<functional>

 const int N=,V=;

 std::string s[N];

 struct Edge {

     int to,id;

     bool vis;

 };

 std::vector<Edge> e[V];

 inline void add_edge(const int &u,const int &v,const int &i) {

     e[u].push_back((Edge){v,i,false});

 }

 inline int idx(const int &ch) {

     return ch-'a';

 }

 bool vis[V];

 int in[V],out[V];

 std::stack<int> ans;

 void dfs(const int &x) {

     for(std::vector<Edge>::reverse_iterator i=e[x].rbegin();i!=e[x].rend();i++) {

         if(i->vis) continue;

         i->vis=true;

         dfs(i->to);

         ans.push(i->id);

     }

 }

 inline void init() {

     for(register int i=;i<V;i++) e[i].clear();

     std::fill(&in[],&in[V],);

     std::fill(&out[],&out[V],);

     std::fill(&vis[],&vis[V],false);

     while(!ans.empty()) ans.pop();

 }

 int main() {

     std::ios_base::sync_with_stdio(false);

     std::cin.tie(NULL);

     register int T;

     for(std::cin>>T;T;T--) {

         init();

         int n;

         std::cin>>n;

         for(register int i=;i<n;i++) {

             std::cin>>s[i];

         }

         std::sort(&s[],&s[n],std::greater<std::string>());

         int start=V;

         for(register int i=;i<n;i++) {

             const int &u=idx(*s[i].begin()),&v=idx(*--s[i].end());

             out[u]++;

             in[v]++;

             add_edge(u,v,i);

             start=std::min(start,std::min(u,v));

         }

         int cnts=,cntt=;

         bool flag=false;

         for(register int i=;i<V;i++) {

             if(out[i]-in[i]==) {

                 cnts++;

                 start=i;

             } else if(in[i]-out[i]==) {

                 cntt++;

             } else if(in[i]!=out[i]){

                 flag=true;

             }

         }

         if(flag||!((cnts==&&cntt==)||(cnts==&&cntt==))) {

             std::cout<<"***"<<std::endl;

             continue;

         }

         dfs(start);

         if((signed)ans.size()!=n) {

             std::cout<<"***"<<std::endl;

             continue;

         }

         std::cout<<s[ans.top()];

         ans.pop();

         while(!ans.empty()) {

             std::cout<<'.'<<s[ans.top()];

             ans.pop();

         }

         std::cout<<std::endl;

     }

     return ;

 }

巴特西

[POJ2337]Catenyms

最新文章

热门文章