首页 > 代码库 > Hdu 1116 Play on Words
Hdu 1116 Play on Words
Problem地址：http://acm.hdu.edu.cn/showproblem.php?pid=1116
一道关于欧拉回路的题。由于刚刚接触欧拉图，所以收集了一些资料：
关于欧拉图的相关定义：
若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉(Euler)回路。
具有欧拉路径的图称为欧拉图（简称E图）。
判断欧拉路是否存在的方法：
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
判断欧拉回路是否存在的方法：
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。资料来源与相关参考：http://www.cnblogs.com/buptLizer/archive/2012/04/15/2450297.html
http://www.cnblogs.com/zhourongqing/archive/2012/07/10/2585235.html
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <queue>using namespace std;const int MAXN = 30;int in[MAXN]; // 对应入度int out[MAXN]; //对应出度int used[MAXN];bool vis[MAXN];int Find( int n ){ if( n!=used[n] ) used[n] = Find( used[n] ); return used[n];}void Merge( int A, int B ){ // 合并 int x = Find(A); int y = Find(B); if( x!=y ) used[y] = x; return ;}int main(){ int T, N; int i,pos; int inJudge, outJudge; bool bug; string temp; cin>>T; while( T-- ){ cin>>N; for( i=0;i<MAXN;i++ ) used[i] = i; memset( in, 0, sizeof(in) ); memset( out, 0, sizeof(out) ); memset( vis, false, sizeof(vis) ); // 初始化 while( N-- ){ cin >> temp; pos = temp.length() - 1; out[ temp[0]-‘a‘ ]++; in[ temp[pos]-‘a‘ ]++; Merge( temp[0]-‘a‘, temp[pos]-‘a‘ ); vis[ temp[0]-‘a‘ ] = vis[ temp[pos]-‘a‘ ] =true; } int counter = 0; // 用于判断有几个图，如果大于1个，那不能满足题目要求 for( i=0;i<=‘z‘-‘a‘;i++ ) if( vis[i] && used[i]==i ) counter ++; if( counter>1 ){ cout << "The door cannot be opened.\n"; continue; } inJudge = outJudge = 0; bug = false; for( i=0;i<=‘z‘-‘a‘;i++ ) if( vis[i] ){ if( in[i]==out[i] ) continue; else if( in[i]-out[i]==1 ) inJudge ++; // 有多少个入度大于出度大1 else if( out[i]-in[i]==1 ) outJudge ++; // 有多少个出度比入度大1 else bug = true; } if( bug ){ cout << "The door cannot be opened.\n"; continue; } if( inJudge==1 && outJudge==1 ){ cout << "Ordering is possible.\n"; continue; } if( !inJudge && !outJudge ){ cout << "Ordering is possible.\n"; continue; } cout << "The door cannot be opened.\n"; } return 0;}
Hdu 1116 Play on Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。