POJ 2337 Catenyms (欧拉图)

本文链接http://i.cnblogs.com/EditPosts.aspx?postid=5402042

题意：

　　给你N个单词，让你把这些单词排成一个序列，使得每个单词的第一个字母和上一个字单词的最后一个字母相同(栗如:acm,malform,mouse)，每个单词最多包含20个小写字母，最多1000个单词。让你输出这个序列，每两个单词之间有个'.'，如果有多个解，输出字典序最小的那组解，如果无解输出"***"。关于字典序，个人感觉就是把最后的序列包括'.'在内看成一个字符串，来比较字典序。举个栗子：aa.ab.ba.aba 的字典序小于 aa.aba.ab.ba因为在索引为 5 的地方第一个序列的'.'小于第二个序列的'a'，而不是仅仅看每个单词的第一个字母。

思路：

　　把每个单词的的两端看成点，把单词看成一条有向边，栗如 atob 表示点 a 到点 b 有一条有向边。那么如果问题有解，则图中一定存在欧拉通路。所以需要首先判断底图是否存在欧拉通路，由单词所建立起来的图是一个有向图，判断有向图是否存在欧拉通路的条件有两个：

第一：底图必须连通，可以用并查集判断；

第二：可以存在2个点出度不等于入度，这两个点中一个出度比入度大1，为路径的起点，另外一个，入度比出度大1，为路径的终点。

如果满足上述两个条件，下来就需要找欧拉路径了，可以采用套圈法，由于要输出字典序，所以需要对所有单词进行排序，由于涉及到排序，刚好可以用前向星来存储图。

注意：

　　第一点：把单词看成边一定是有向的，判定条件不要和无向图搞混。

　　第二点：提前排好序，不要在每次选择扩展路径时才选择字典序最小的，容易TLE。

　　第三点：如果按照从升序，那么答案应该是反过来的，存在栈中就行了。

　　第四点：题目中给的单词是随机的，所以需要找到起点，如果图中存在欧拉回路，即所有点的入度等于出度，那么找到出现的单词中首字母最小的就可以作为路径的起点了。如果不存在欧拉回路，仅存在欧拉通路，即存在确定的起点和确定的终点，那么起点不应该是字母最小的点了，而是确定的那个起点，即出度比入度大 1 的点。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <stack>
  8 #include <queue>
  9 using namespace std;
 10 
 11 const int maxV = 26;
 12 const int maxE = 1000;
 13 int indeg[maxV + 7];//入度
 14 int outdeg[maxV + 7];//出度
 15 int head[maxV + 7];//确定起点为vi的第一条边的位置
 16 int pre[maxV + 7];
 17 int vis[maxE + 7];
 18 int E, V;
 19 //并查集
 20 void initPre()
 21 {
 22     for(int i = 0; i <= maxV; i++)pre[i] = i;
 23 }
 24 
 25 int Find(int x)
 26 {
 27     return x == pre[x] ? x : pre[x] = Find(pre[x]);
 28 }
 29 
 30 void mix(int x, int y)
 31 {
 32     int fx = Find(x);    
 33     int fy = Find(y);    
 34     if(fx > fy) pre[fx] = fy;    
 35     if(fx < fy) pre[fy] = fx;
 36 }
 37 //前向星的结构
 38 struct EdgeNode
 39 {
 40     int from;
 41     int to;
 42     char w[33];//单词
 43 }edges[maxE + 7];
 44 
 45 int minst;
 46 bool isEuler()//是否能形成欧拉通路
 47 {
 48     int flag1 = 0;
 49     int flag2 = 0;
 50     for(int i = 1; i <= maxV; i++)
 51     {
 52         if(indeg[i] != outdeg[i])
 53         {
 54             if(indeg[i] == outdeg[i] + 1) flag1++; 
 55             else if(indeg[i] == outdeg[i] - 1) flag2++,minst = i;//如果存在出度比入度大 1 的点，即为起点
 56             else return false;
 57         } 
 58     }
 59     if(flag1 == 1 && flag2 == 1 || flag1 == 0 && flag2 == 0) return true;
 60     return false;
 61 }
 62 
 63 bool isConnct()//连通性判断
 64 {
 65     int cnt = 0;
 66     for(int i = 1; i <= maxV; i++)
 67         if( (outdeg[i] != 0 || indeg[i] != 0) && pre[i] == i)
 68             cnt++;
 69     if(cnt == 1)return true;
 70     return false;
 71 }
 72 
 73 stack<int> ans;
 74 void eulerDFS(int now)
 75 {
 76     for(int k = head[now]; edges[k].from == now && k <= E; k++)//优先访问由字典序比较小的单词构成的边
 77     {
 78         if(!vis[k])
 79         {
 80             vis[k] = 1;
 81             eulerDFS(edges[k].to);
 82             ans.push(k);    //回溯时,压入栈的一定是字典序较大的
 83         }    
 84     }    
 85 }
 86 
 87 int cmp(EdgeNode A, EdgeNode B)
 88 {
 89     return strcmp(A.w, B.w) < 0;
 90 }
 91 
 92 int main()
 93 {
 94     int T;
 95     scanf("%d", &T);
 96     while(T--)
 97     {
 98         memset(&edges, 0, sizeof(EdgeNode));
 99         memset(indeg, 0, sizeof(indeg));
100         memset(outdeg, 0, sizeof(outdeg));
101         memset(vis, 0, sizeof(vis));
102         initPre();
103         scanf("%d", &E);
104         minst = maxV + 1;
105         for(int i = 1; i <= E; i++)
106         {
107             scanf("%s", edges[i].w);
108             edges[i].from = edges[i].w[0] - 'a' + 1;                  
109             edges[i].to = edges[i].w[strlen(edges[i].w) - 1] - 'a' + 1;
110             outdeg[edges[i].from]++;
111             indeg[edges[i].to]++;
112             mix(edges[i].from, edges[i].to);
113             minst = min(minst, edges[i].from);//默认首字母较小的为起点
114         }
115         sort(edges + 1, edges + E + 1, cmp);//按照字典序升序排序
116         memset(head, -1, sizeof(head));
117         head[edges[0].from] = 0;
118         for(int i = 1; i<= E; i++)//构造head数组
119         {
120             if(edges[i].from != edges[i - 1].from) head[edges[i].from] = i;
121         } 
122         if(isEuler() && isConnct())
123         {
124             eulerDFS(minst);
125             int flag = 0;
126             while(!ans.empty())
127             {
128                 printf((flag++) ? ".%s":"%s", edges[ans.top()].w);
129                 ans.pop();
130             }
131             printf("
");
132         }
133         else
134             printf("***
");
135     }
136     return 0;
137 }