uva 10441（poj 2337 欧拉通路）-白红宇

uva 10441（poj 2337 欧拉通路）

阅读量：6957 次

发布时间：2019-06-27

本文共 2016 字，大约阅读时间需要 6 分钟。

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

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

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

（2）当前图是弱连通的。（就是当前图换成有向图是连通的）

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

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

代码如下：

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 
      
        10 #include 
       
         11 #include 
        
          12 #include 
         
           13 #include 
          
            14 #include 
           
             15 #include 
            
              16 #include 
             
               17 #include 
              
                18 #include 
               
                 19 #include 
                 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
                 
                   pii; 27 typedef pair
                  
                    puu; 28 typedef pair
                   
                     pid; 29 typedef pair
                    
                      pli; 30 typedef pair
                     
                       pil; 31 typedef pair
                      
                        pis; 32 33 const int INF = 0x3f3f3f3f; 34 const double eps = 1E-6; 35 const int LEN = 30; 36 vector
                       
                         Map[LEN]; 37 int mp[LEN][LEN]; 38 int n, od[LEN], id[LEN], st, ed, top; 39 string ans[10002]; 40 map
                        
                          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
                         
                          1 || y>1 || cc>1 || x+y==1) return false; 77 if(x+y==0)for(int i=0; i
                          
                           > T; 89 while(T--){ 90 cin >> n; 91 for(int i=0; i
                           
                            > 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

转载于:https://www.cnblogs.com/shu-xiaohao/p/3535741.html

你可能感兴趣的文章