题意:
给定n个单词, 问是否存在一条欧拉通路(如acm,matal,lack), 如果存在, 输出字典序最小的一条。
分析:
这题可以看作http://www.cnblogs.com/Jadon97/p/7210278.html升级版本(那题只问是否存在, 这题需要输出路径)
判断有向图的欧拉通路, 主要用到出入度的判定和连通性。
有向图欧拉通路判定方法:图连通;除2个端点外其余节点入度=出度;1个端点入度比出度大1;一个端点入度比出度小1 或 所有节点入度等于出度
DFS求解算法:选择一个正确的起点,用DFS算法遍历所有的边(每条边只遍历一次),遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来,这组边的排列就组成了一条欧拉通路或者回
#include<cstdio> #include<iostream> #include<vector> #include<string> #include<cstring> #include<algorithm> using namespace std; string word[2010]; struct node { int to, index; node(int _to, int _index): to(_to), index(_index) {}; }; vector<node> G[30]; int degree[30], vis[2010], used[26], ans[2010]; int n, tot; int st; int id(int a) { return a - 'a'; } void dfs(int u) { // cout << word[index] << "\n"; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i].to, index = G[u][i].index; if(!vis[index]) { vis[index] = 1; dfs(v); ans[tot++] = index; } } } bool judge() { int cc1 = 0, cc2 = 0; //cc1 出度>入度 cc2 入度>出度 for(int i = 0; i < 26; i++) { if(used[i]) { if(degree[i] != 0) { if(degree[i] == 1) { cc1++, st = i;//如果出度大于入度, 那么以该点为起点 } else if(degree[i] == -1) { cc2++; } else { return false; } } } } if((cc1 || cc2) && cc1 + cc2 != 2) //有出度入度不等的点, 而且不止2个 { return false; } return true; } int main() { // freopen("1.txt","r", stdin); int T; cin >> T; while(T--) { for(int i = 0; i < 30; i++) G[i].clear(); memset(used, 0, sizeof(used)); memset(vis, 0, sizeof(vis)); memset(degree, 0, sizeof(degree)); tot = 0; cin >> n; for(int i = 0; i < n; i++) { cin >> word[i]; } sort(word, word + n); st = 100; for(int i = 0; i < n; i++) { int u = id(word[i][0]), v = id(word[i][word[i].size()-1]); G[u].push_back(node(v,i)); if(u < st) st = u; //从字典序最小的开始遍历 used[u] = used[v] = 1; //记录u,v是用过的 degree[u]++, degree[v]--; //出度++, 入度-- } if(!judge()) { printf("***\n"); continue; } dfs(st); if(tot != n) //不连通 { printf("***\n"); continue; } else { cout << word[ans[tot-1]]; for(int i = tot - 2; i >= 0; i--)//反向输出路径 { cout <<"." << word[ans[i]] ; } puts(""); } } }
转载于:https://www.cnblogs.com/Jadon97/p/8540184.html