uva 10441(poj 2337 欧拉通路)

题意:有一些单词他们之间只要满足A的最后一个字母和B的第一个字母相同。就能建立A.B的关系。然后问你能不能找到把所有单词连成一串且所有单词都出现一次。

思路:其实题意就是能不能在一张无向图中找到一条欧拉通路。我们知道在无向图中一张图存在欧拉通路的条件是:

(1)所有结点入度=出度或有一个节点入度-出度=1有另一个节点出度-入度=1其他节点入度-出度。

(2)当前图是弱连通的。(就是当前图换成有向图是连通的)

然后我们在用dfs输出欧拉道路就可以了。

至于dfs的过程是这样的每走过一条边就标记它。然后在回溯的时候记录路径。

代码如下:

uva 10441(poj 2337 欧拉通路)
  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-01-28 10:25
  5  * Filename     : uva_10441.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 
 25 typedef long long ll;
 26 typedef pair<int, int> pii;
 27 typedef pair<unsigned int,unsigned int> puu;
 28 typedef pair<int, double> pid;
 29 typedef pair<ll, int> pli;
 30 typedef pair<int, ll> pil;
 31 typedef pair<int, string> pis;
 32 
 33 const int INF = 0x3f3f3f3f;
 34 const double eps = 1E-6;
 35 const int LEN = 30;
 36 vector<pis> Map[LEN];
 37 int mp[LEN][LEN];
 38 int n, od[LEN], id[LEN], st, ed, top;
 39 string ans[10002];
 40 map<string, int> vis, mc;
 41 
 42 bool cmp(pis a, pis b){return a.second < b.second;}
 43 
 44 void dfs(int v)
 45 {
 46     for(int i=0; i<Map[v].size(); i++){
 47         string str = Map[v][i].second;
 48         int nv = Map[v][i].first;
 49         if(vis[str] < mc[str]){
 50             vis[str] ++;
 51             dfs(nv);
 52             ans[top++] = str;
 53         }
 54     }
 55 }
 56 
 57 bool is[LEN];
 58 void isd(int x){
 59     is[x] = true;
 60     for(int i=0; i<LEN; i++){
 61         if(mp[x][i] && !is[i]) isd(i);
 62     }
 63 }
 64 
 65 bool check()
 66 {
 67     memset(is, false, sizeof is);
 68     int x(0), y(0), cc(0);
 69     for(int i=0; i<26; i++){
 70         if(id[i]+od[i] && !is[i]){isd(i);cc++;}
 71         if(id[i] == od[i]) continue;
 72         else if(id[i]-od[i]==1) {x ++;ed = i;}
 73         else if(od[i]-id[i]==1) {y ++;st = i;}
 74         else return false;
 75     }
 76     if(x>1 || y>1 || cc>1 || x+y==1) return false;
 77     if(x+y==0)for(int i=0; i<LEN; i++)if(id[i]){st = ed = i;break;}    
 78     return true;
 79 }
 80 
 81 int main()
 82 {
 83 //    freopen("in.txt", "r", stdin);
 84     
 85     ios::sync_with_stdio(false);
 86     int T, a, b;
 87     string str;
 88     cin >> T;
 89     while(T--){
 90         cin >> n;
 91         for(int i=0; i<LEN; i++)Map[i].clear();
 92         memset(od, 0, sizeof od);
 93         memset(id, 0, sizeof id);
 94         memset(mp, 0, sizeof mp);
 95         mc.clear();vis.clear();
 96         for(int i=0; i<n; i++){
 97             cin >> str;
 98             a = str[0]-a;b = str[str.size()-1]-a;
 99             od[a]++;id[b]++;
100             mp[a][b] = mp[b][a] = 1;
101             if(!mc.count(str)) mc[str] = 1;
102             else mc[str] ++;
103             Map[a].PB(MP(b, str));
104         }
105         for(int i=0; i<26; i++)sort(Map[i].begin(), Map[i].end(), cmp);
106         if(check()){
107             top = 0;
108             dfs(st);
109             for(int i=top-1; i>=0; i--){
110                 cout << ans[i];
111                 if(i!=0)cout << ".";
112             }
113         }else cout << "***";
114         cout << endl;
115     }
116     return 0;
117 }
View Code

uva 10441(poj 2337 欧拉通路)

上一篇:visio 到处流程图


下一篇:一致hash算法