欧拉回路 ZQUOJ21349&&POJ2337 Catenyms

Description

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 first letter of the second. For example, the following are catenyms:

dog.gophergopher.ratrat.tigeraloha.alohaarachnid.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

aloha

arachnid

dog

gopher

rat

tiger

oak

maple

elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger

***

题意：给你一些单词，能否将这些单词首尾连接起来，即前一个单词的最后一个字母和后一个单词的第一个字母相同，若能输出该序列，若有多种则按字典序输出该序列。是欧拉路径的题，但这次要判断存在欧拉路径后输出字典序最小的路径，先把单词按字典序排序，然后判断是欧拉回路还是只是欧拉通路，如果是欧拉回路，直接从第0号单词开始搜，否则，找到出度比入度大1的那个单词开始搜。

分析：并查集+欧拉回路

如果将每一个单词的首字母和尾字母看成节点，每个单词看成一个线段的话，若满足上述条件，就会构成一个欧拉图，然后就找出符合条件的欧拉路径。

（1）构图。以为要按字典序输出，所以单词输入完毕后，进行一趟排序，有大到小排，若采用头插法，邻接表建立后，后面的节点就会自然就会按字典序排好。

（2）判断有没有欧拉路径。作为有向图，有欧拉路径的从分条件是：在连通的前提下，始点的出度比入度大一且终点的入度比出度大一且其他的顶点出度等于入度，或者所有顶点出度等于入度。

（3）输出欧拉路径。

有关欧拉回路的算法：http://blog.chinaunix.net/uid-26380419-id-3164913.html

http://blog.csdn.net/shahdza/article/details/6630108

AC代码：

View Code

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 #include<algorithm>
  5 using namespace std;
  6 typedef struct
  7 {
  8     int y,next;
  9     char s[21];
 10 }Node;
 11 Node e[1000];
 12 int ans,begin,end;
 13 int first[27],in[27],out[27],vis[1000],flag[27];
 14 int father[27],degree[27];
 15 char path[1000][27];
 16 int cmp(Node a,Node b)
 17 {
 18     return strcmp(a.s,b.s)>0;
 19 }
 20 int find(int x)
 21 {
 22     if(x!=father[x])
 23         father[x]=find(father[x]);
 24     return father[x];
 25 }
 26 int judge()  //判断是否满足欧拉条件。0不满足，1欧拉回路，2欧拉通路
 27 { 
 28     int i,j,k,odd=0;
 29     for(i=0;i<26;i++)  //判断有向图欧拉
 30     {
 31         if(!flag[i])
 32             continue;
 33         degree[i]=in[i]-out[i];
 34         if(abs(degree[i])>1)
 35             return 0;
 36         if(degree[i]<0)
 37             begin=i;   //起点
 38         if(degree[i]>0)
 39             end=i;     //终点
 40         if(degree[i]%2)
 41             odd++;
 42         if(odd>2)
 43             return 0;
 44     }
 45     for(i=0;i<26;i++)
 46         if(flag[i])
 47         {
 48             j=i;
 49             break;
 50         }
 51     k=find(j);
 52     for(i=k+1;i<26;i++)   //判断连通性
 53     {
 54         if(!flag[i])
 55             continue;
 56         if(k!=find(i))
 57             return 0;
 58     }
 59     if(odd==0)  //有欧拉回路
 60     {
 61         begin=j;
 62         return 1;
 63     }
 64     return 2;
 65 }
 66 void dfs(int x,int id)   //深搜寻找欧拉路径
 67 {
 68     int i;
 69     for(i=first[x];i!=-1;i=e[i].next)
 70         if(!vis[i])
 71         {
 72             vis[i]=1;
 73             dfs(e[i].y,i);
 74         }
 75     if(id!=-1)
 76         strcpy(path[ans++],e[id].s);   //最先进去的肯定是终点
 77 }
 78 int main()
 79 {
 80     int t,m,n,i,x,y,fx,fy,k;
 81     scanf("%d",&t);
 82     while(t--)
 83     {
 84         scanf("%d",&n);
 85         for(i=0;i<n;i++)
 86             scanf("%s",e[i].s);
 87         //题目要求是字典顺序，但是我是用前插链表，这时的顺序恰好会相反  
 88         sort(e,e+n,cmp);  //所以排序时从大到小，这样刚刚会是字典顺序 
 89         ans=0;
 90         memset(in,0,sizeof(in));
 91         memset(out,0,sizeof(out));
 92         memset(vis,0,sizeof(vis));
 93         memset(flag,0,sizeof(flag));
 94         memset(first,-1,sizeof(first));
 95         for(i=0;i<26;i++)
 96             father[i]=i;
 97         for(i=0;i<n;i++)
 98         {
 99             m=strlen(e[i].s);
100             x=e[i].s[0]-'a';
101             y=e[i].s[m-1]-'a';
102             in[y]++;   //入度
103             out[x]++;  //出度
104             flag[x]=1;
105             flag[y]=1;
106             //***建边***
107             e[i].y=y;
108             e[i].next=first[x];
109             first[x]=i;
110             //***建边***
111             fx=find(x);
112             fy=find(y);
113             if(fx!=fy)
114                 father[fx]=fy;
115         }
116         k=judge();  
117         if(k==0)
118             printf("***\n");
119         else
120         {
121             dfs(begin,-1);
122             printf("%s",path[ans-1]);
123             for(i=ans-2;i>=0;i--)
124                 printf(".%s",path[i]);
125             printf("\n");
126         }
127     }
128     return 0;
129 }