POJ 2337 【欧拉路径<包含输出>】.cpp

题意：

　　给出n个字母

　　问是否可以全部头尾相接，输出按字典序排列

思路：

　　用套圈法求出欧拉回路

先把单词读入

排序保证最后结果是按字典序的

用并查集看是否连通

根据入度和出度看是否是欧拉路径，如果有必要也要找出起点

用套圈法求出欧拉路径

输出结果　　

Tips：

　　※ 不能用cin cout

　　 ※ 注意不能直接由 ansi == n 来判断是否有欧拉路径..

而要由出度和入度的关系来判断..

因为如果出现是出度-入度 = 1 且入度-出度 = 1的时候要保证出度-入度 = 1的点是起点~
否则即使连通也不能证明存在欧拉路径..

※ 用并查集检查是否连通以及从每一个已知的起点开始dfs的时候可以for(i : a~z)而不是for(i: 0~n)

这样可以降低时间复杂度~~

Code：

View Code

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 const int MAXN = 1010;
  6 #define clr(x) memset(x, 0, sizeof(x));
  7 #define INF 0x1f1f1f1f
  8 
  9 struct Edge
 10 {
 11     int to;
 12     int next;
 13 
 14 }edge[1000000];
 15 int tot;
 16 int head[MAXN];
 17 
 18 void add(int s, int u)
 19 {
 20     edge[tot].to = u;
 21     edge[tot].next = head[s];
 22     head[s] = tot++;
 23 }
 24 
 25 struct Inf
 26 {
 27     char arr[25];
 28     bool operator < (const Inf&a) const {
 29         return strcmp(arr, a.arr) > 0;
 30     }
 31 }inf[MAXN];
 32 
 33 bool vis[MAXN];
 34 int ans[MAXN], ansi;
 35 void dfs(int x) {
 36     for(int i = head[x]; i; i = edge[i].next) {
 37         if(!vis[i]) {
 38             vis[i] = true;
 39             dfs(edge[i].to);
 40             ans[ansi++] = i;
 41         }
 42     }
 43 }
 44 
 45 int pre[26];
 46 bool v[26];
 47 int in[26], out[26];
 48 int find(int x)
 49 {
 50     return pre[x] == x?x:(pre[x] = find(pre[x]));
 51 }
 52 
 53 void ini()
 54 {
 55     clr(head);
 56     tot = 1;
 57  //  memset(head, 0xff, sizeof(head));
 58  //  tot = 0;
 59     clr(vis);
 60     ansi = 0;
 61     for(int i = 0; i < 26; ++i)
 62         pre[i] = i;
 63     clr(v);
 64     clr(in);
 65     clr(out);
 66 }
 67 
 68 int main()
 69 {
 70   //  freopen("e:\\acm\\in.txt", "r", stdin);
 71     int T, n;
 72     int a, b, len;
 73     bool flag;
 74     int _f, _ff, _fff, r;
 75     while(EOF != scanf("%d", &T))
 76     while(T--) {
 77         scanf("%d", &n);
 78         ini();
 79         flag = true;
 80         for(int i = 0; i < n; ++i)
 81             scanf("%s", inf[i].arr);
 82 
 83         sort(inf, inf+n);
 84         for(int i = 0; i < n; ++i) {
 85             len = strlen(inf[i].arr);
 86             a = inf[i].arr[0]-'a', b = inf[i].arr[len-1]-'a';
 87             add(a, b);
 88             in[b]++, out[a]++, v[a] = v[b] = true;
 89             int fa = find(a);
 90             int fb = find(b);
 91             if(fa < fb) pre[fb] = fa;
 92             else pre[fa] = fb;
 93         }
 94         _f = -1;
 95         for(int i = 0; i < 26; ++i)
 96         if(v[i] && _f == -1) _f = find(i);
 97         else if(v[i] && _f != find(i)) {
 98             flag = false;
 99             break;
100         }
101         if(!flag) {
102             puts("***");
103             continue;
104         }
105         _f = 0, _ff = 0, _fff = 0;
106         for(int i = 0; i < 26; ++i)
107         if(v[i]) {
108             if(in[i]-out[i] == 1) _f++;
109             else if(out[i]-in[i] == 1) {
110                 r = i;
111                 _ff++;
112             } else if(out[i] != in[i]) _fff++;
113         }
114         if(_fff == 0 && _f == 1 && _ff == 1) {
115             dfs(r);
116             for(int i = ansi-1; i >= 0; --i)
117                 printf("%s%c", inf[ans[i]-1].arr, i == 0?'\n':'.');
118         } else if(_fff == 0 && _f == 0 && _fff == 0) {
119             int i;
120             for(i = 0; i < 26; ++i)
121             if(v[i]) break;
122             dfs(i);
123             for(int i = ansi-1; i >= 0; --i)
124                 printf("%s%c", inf[ans[i]-1].arr, i == 0?'\n':'.');
125         } else puts("***");
126     }
127     return 0;
128 }

链接：http://poj.org/problem?id=2337