poj 2337

深碍√TFBOYSˉ_ 2021-10-18 18:44 159阅读 0赞

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:

dog.gopher
    
    gopher.rat
    
    rat.tiger
    
    aloha.aloha
    
    arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,  
  
aloha.aloha.arachnid.dog.gopher.rat.tiger  
  
Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

Input

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

Output

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "\*\*\*" if there is no solution.

Sample Input

2
    6
    aloha
    arachnid
    dog
    gopher
    rat
    tiger
    3
    oak
    maple
    elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger
    ***
    
    这道题本人使用了kuangbin的代码，注意，这道题是深入理解欧拉路径怎么求
    在前面一道题（poj2230）中，我们在求欧拉“回路”时利用了记录节点的方式，这是因为欧拉回路保证每一次遍历节点的时候，如果成环，也一定能回来，但是这里不能记录节点
    因为一旦我们记录节点，如果这条欧拉通路中有环，不能保证我们能按顺序dfs出来，而且这道题最恶心的地方是字典序，所以我一开始想的是用邻接表存图，然后对每个顺序开头的字母进行排序
    但是这样同样出现了“一旦成环”的问题，这也是欧拉回路与欧拉路径的最大区别，所以显然，欧拉回路简单的多，但是欧拉路径就难了一个层级，kuangbin用了前向星，为什么会用这个东西，
    后来我理解了一下，就是为了“字典序”，字典序必须对每一个单词都要排一遍，同时前向星能够保证不出现我们这种“成环”的问题。
    同时，注意我们判断欧拉路径的时候，必须保证这个图是连通的，这里kuangbin非常巧妙地在dfs函数中记录了边的条数，一旦边不等于输入，一定不连通，真的巧妙，哎哎哎啊，本人还有很长一段路要走。
    先贴我的错误代码，如果有人能用邻接表做的话能够评论指正，我是记录了节点，现在看来，这种存图方式应该肯定不能适用于这一类问题。

//coolwx的错误代码
    #include <iostream>
    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <cstring>
    using namespace std;
    int n;
    vector<string> record;
    struct node{
          int to;
          string cost;
          bool ok;
          node(int x,string y,bool z);
    };
    node::node(int x,string y,bool z){
        to=x;
        cost=y;
        ok=z;
    }
    bool vis[27];
    pair<int,int> dushu[27];
    vector<node> alphabet[27];
    void dfs(int u)
    {
        for(int i=0;i<alphabet[u].size();i++)
        {
            if(alphabet[u][i].ok==false)
            {    
                record.push_back(alphabet[u][i].cost);
                alphabet[u][i].ok=true;
                dfs(alphabet[u][i].to);
                
            }
        }    
        
    }
    bool cmp(node a,node b)
    {
        return a.cost<b.cost;
    }
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            record.clear();
            for(int i=0;i<26;i++)
            {
                alphabet[i].clear();
                dushu[i]=make_pair(0,0);
                vis[i]=false;
            }
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                string x;
                cin>>x; 
                int start=x[0]-'a';
                int end=x[x.length()-1]-'a';
                vis[start]=true;
                vis[end]=true;
                alphabet[start].push_back(node(end,x,false));
                dushu[start].first+=1;
                dushu[end].second+=1;
            }
            int nn=0;
            for(int i=0;i<26;i++)
            {
                if(vis[i])
                nn++;
            }
            int flag=0;
            int ssum=0;
            int estart=100,eend=100;
            for(int i=0;i<26;i++)
            {
                if(dushu[i].first==0&&dushu[i].second==0)
                continue;
                if(dushu[i].first-dushu[i].second==1)
                estart=i;
                else if(dushu[i].second-dushu[i].first==1)
                eend=i;
                else if(dushu[i].first==dushu[i].second)
                ssum++;
                else
                {
                    break;
                }
            }
            if(ssum==nn||ssum==nn-2)
            flag=1;
            if(flag==0)
            {
                printf("***\n");
                continue;
            }
            else
            {
                for(int i=0;i<26;i++)
                {
                    sort(alphabet[i].begin(),alphabet[i].end(),cmp);
                }
                if(eend!=100&&estart!=100)
                {
                    dfs(estart);
                }
                else
                {
                    for(int i=0;i<26;i++)
                    {
                        if(alphabet[i].size()!=0)
                        {
                            dfs(i);
                            break;
                        }
                    }
                }
                if(record.size()!=n)
                {printf("***\n");
                continue;
                }
                else
                for(int i=0;i<record.size()-1;i++)
                {
                    cout<<record[i]<<'.';
                }
                cout<<record[record.size()-1]<<'\n';
            }
        }
    }

再贴kuangbin的正解，网上大多数都是使用了前向星的做法，今天也算理解了一遍。

/* ***********************************************
    Author        :kuangbin
    Created Time  :2014-2-3 13:12:43
    File Name     :E:\2014ACM\专题学习\图论\欧拉路\有向图\POJ2337.cpp
    ************************************************ */
    
    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <math.h>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    struct Edge
    {
        int to,next;
        int index;
        bool flag;
    }edge[2010];
    int head[30],tot;
    void init()
    {
        tot = 0;
        memset(head,-1,sizeof(head));
    }
    void addedge(int u,int v,int index)
    {
        edge[tot].to = v;
        edge[tot].next = head[u];
        edge[tot].index = index;
        edge[tot].flag = false;
        head[u] = tot++;
    }
    string str[1010];
    int in[30],out[30];
    int cnt;
    int ans[1010];
    void dfs(int u)
    {
        for(int i = head[u] ;i != -1;i = edge[i].next)
            if(!edge[i].flag)
            {
                edge[i].flag = true;
                dfs(edge[i].to);
                ans[cnt++] = edge[i].index;
            }
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        int T,n;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            for(int i = 0;i < n;i++)
                cin>>str[i];
            sort(str,str+n);//要输出字典序最小的解，先按照字典序排序
            init();
            memset(in,0,sizeof(in));
            memset(out,0,sizeof(out));
            int start = 100;
            for(int i = n-1;i >= 0;i--)//字典序大的先加入
            {
                int u = str[i][0] - 'a';
                int v = str[i][str[i].length() - 1] - 'a';
                addedge(u,v,i);
                out[u]++;
                in[v]++;
                if(u < start)start = u;
                if(v < start)start = v;
            }
            int cc1 = 0, cc2 = 0;
            for(int i = 0;i < 26;i++)
            {
                if(out[i] - in[i] == 1)
                {
                    cc1++;
                    start = i;//如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发
                }
                else if(out[i] - in[i] == -1)
                    cc2++;
                else if(out[i] - in[i] != 0)
                    cc1 = 3;
            }
            if(! ( (cc1 == 0 && cc2 == 0) || (cc1 == 1 && cc2 == 1) ))
            {
                printf("***\n");
                continue;
            }
            cnt = 0;
            dfs(start);
            if(cnt != n)//判断是否连通
            {
                printf("***\n");
                continue;
            }
            for(int i = cnt-1; i >= 0;i--)
            {
                cout<<str[ans[i]];
                if(i > 0)printf(".");
                else printf("\n");
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/coolwx/p/11181226.html