POJ 2337 欧拉回路+欧拉路径+判断欧拉回路和路径

本文主要是介绍POJ 2337 欧拉回路+欧拉路径+判断欧拉回路和路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//
//  main.cpp
//  POJ 2337 欧拉路径
//
//  Created by 郑喆君 on 8/7/14.
//  Copyright (c) 2014 itcast. All rights reserved.
//#include<cstdio>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int int_max = 0x07777777;
const int int_min = 0x80000000;
int smaller (int a, int b) { return (a > b ? b : a); }
int bigger (int a, int b) { return (a > b ? a : b); }
const int maxn = 100;
struct Edge {int from,to;Edge(int _from, int _to):from(_from),to(_to){}
};
vector<Edge> es;
vector<int> G[maxn];
void addedge (int from, int to){es.push_back(Edge(from, to));G[from].push_back(es.size()-1);
}
int root[1100];
int tot;
vector<int> g[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
void dfs (int u){pre[u] = lowlink[u] = ++dfs_clock;S.push(u);for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(!pre[v]){dfs(v);lowlink[u] = smaller(lowlink[u], lowlink[v]);}else if(!sccno[v]){lowlink[u] = smaller(lowlink[u], pre[v]);}}if(lowlink[u]==pre[u]){scc_cnt++;while (true) {int x = S.top();S.pop();sccno[x] = scc_cnt;if(x==u) break;}}
}
void find_scc (int nn){dfs_clock = scc_cnt = 0;memset(sccno, 0, sizeof(sccno));memset(pre, 0, sizeof(pre));for(int i = 0; i < nn; i++){if(!pre[i] && g[i].size()) dfs(i);}
}
int compare(const void *a,const void *b)
{return (strcmp((const char*)a,(const char*)b));
}
int n;
char ss[1100][25];
int vis[1100];
void dfss(int x, int pre){for(int i = 0; i < G[x].size(); i++){if(!vis[G[x][i]]){vis[G[x][i]] = 1;dfss(es[G[x][i]].to, G[x][i]);}}if(pre!=-1) root[tot++] = pre;
}
int main(int argc, const char * argv[])
{int T;scanf("%d",&T);while(T--){scanf("%d", &n);for(int i = 0; i < maxn; i++) g[i].clear();for(int i = 0; i < n; i++) {scanf("%s", ss[i]);g[ss[i][0]-'a'].push_back(ss[i][strlen(ss[i])-1]-'a');g[ss[i][strlen(ss[i])-1]-'a'].push_back(ss[i][0]-'a');}find_scc(26);if(scc_cnt > 1) {cout << "***" << endl; continue;}qsort(ss, n, sizeof(char)*25, compare);es.clear();for(int i = 0; i < maxn; i++) G[i].clear();for(int i = 0; i < n; i++){addedge(ss[i][0]-'a',ss[i][strlen(ss[i])-1]-'a');}int dayu = 0;int xiaoyu = 0;int rudu[26],chudu[26];memset(rudu, 0, sizeof(rudu));memset(chudu, 0, sizeof(chudu));for(int i = 0; i < 26; i++){if(G[i].size()){for(int j = 0; j < G[i].size(); j++){chudu[i]++;rudu[es[G[i][j]].to]++;}}}int flag = 1;for(int i = 0; i < 26; i++){if(abs(rudu[i]-chudu[i]) > 1){flag = 0;break;}if(rudu[i]-chudu[i]==1) dayu++;if(chudu[i]-rudu[i]==1) xiaoyu++;}if(!(flag==1 && ((dayu==1&&xiaoyu==1)||(dayu==0&&xiaoyu==0)))){cout << "***" << endl; continue;}int start = es[0].from;for(int i = 0; i < 26; i++) if(chudu[i]-rudu[i]==1) start = i;memset(vis, 0, sizeof(vis));tot = 0;dfss(start,-1);for(int i = tot-1; i>0; i--) printf("%s.", ss[root[i]]);printf("%s\n", ss[root[0]]);}
}

这篇关于POJ 2337 欧拉回路+欧拉路径+判断欧拉回路和路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---