首页 > 代码库 > UVa10129 Play on Words (欧拉路径)
UVa10129 Play on Words (欧拉路径)
链接: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 (欧拉路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。