首页 > 代码库 > UVa10129 Play on Words (欧拉路径)

UVa10129 Play on Words (欧拉路径)

2024-08-11 17:12:35   218人阅读

链接：http://acm.hust.edu.cn/vjudge/problem/19492
分析：
　　欧拉路径：https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98
　　

技术分享

技术分享 

技术分享

技术分享

只用关注每个单词的首尾字母就够了其它的没有用，从首字母向尾字母连边，看是否能形成一个欧拉路径，用DFS找连通块的方式判断是否是连通图，然后如果每个点的出入度数相等则存在欧拉回路当然就有欧拉路径，否则查看是否存在两个点出入度数不相等，且其中一个点的出入度数相差1，那么另一个点的出入度数差肯定与之互补。

 1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5  6 const int maxn = 1000 + 5; 7  8 int deg[256], vis[256]; 9 vector<int> G[256];10 11 void dfs(int u) {12     vis[u] = 1;13     for (int i = 0; i < G[u].size(); i++)14         if (vis[G[u][i]]) continue;15         else dfs(G[u][i]);16 }17 18 int main() {19     int T;20     scanf("%d", &T);21     while (T--) {22         for (int i = ‘a‘; i <= ‘z‘; i++) deg[i] = 0;23         for (int i = ‘a‘; i <= ‘z‘; i++) G[i].clear();24         int n;25         scanf("%d", &n);26         char word[maxn];27         for (int i = 0; i < n; i++) {28             scanf("%s", word);29             char c1 = word[0], c2 = word[strlen(word) - 1];30             deg[c1]++, deg[c2]--;31             G[c1].push_back(c2), G[c2].push_back(c1);32         }33         int cnt = 0;34         for (int ch = ‘a‘; ch <= ‘z‘; ch++) vis[ch] = 0;35         for (int ch = ‘a‘; ch <= ‘z‘; ch++)36             if (vis[ch] == 0 && G[ch].size() > 0) {37                 cnt++; if (cnt > 1) break;38                 dfs(ch);39             }40         vector<int> d;41         for (int ch = ‘a‘; ch <= ‘z‘; ch++)42             if (deg[ch] != 0) d.push_back(deg[ch]);43         bool ok = false;44         if (cnt == 1 && (d.empty() || (d.size() == 2 && (d[0] == 1 || d[0] == -1)))) ok = true;45         if (ok) printf("Ordering is possible.\n");46         else printf("The door cannot be opened.\n");47     }48     return 0;49 }

 



UVa10129 Play on Words (欧拉路径)






























        

            
                
                  
                
                

                    联系

                    我们