[UVa] 10129 - Play on Words

題目網址: http://goo.gl/BHfaFv

題意: 給定 n 個字，如果兩個字A、B，A的字尾等於B的字首，A就能接著B，問是否有方法能夠串連所有的字串。


解法: Eulerian circuit，字母是點，字是邊。

TAG: Eulerian circuit

注意: 是有向圖喔

程式碼:

	/**
	* Tittle: 10129 - Play on Words
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/04
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 30
	#define M 100005
	class Edge {
	public:
	int v, nxt;
	Edge( int _v=0, int _nxt=-1 ): v(_v), nxt(_nxt) {}
	};
	// declarations
	int t;
	int n;
	int indeg[N];
	int outdeg[N];
	int ecnt;
	int ehead[N];
	Edge edge[2*M];
	bool enable[N];
	// functions
	void addEdge( int u, int v )
	{
	edge[ecnt] = Edge( v, ehead[u] );
	ehead[u] = ecnt++;
	}
	bool vis[N];
	void dfs( int u )
	{
	if( vis[u] ) return ;
	vis[u] = true;
	int ne;
	for( ne=ehead[u]; ne!=-1; ne=edge[ne].nxt ) {
	dfs( edge[ne].v );
	}
	}
	inline int abs( int x )
	{
	if( x < 0 ) return -x;
	return x;
	}
	bool check( void )
	{
	// check for connectivity
	clr( vis, false );
	FOR( i, 0, 25 ) if( enable[i] && !vis[i] ) {
	dfs( i );
	break;
	}
	FOR( i, 0, 25 )
	if( enable[i] && !vis[i] ) return false;
	// check for euler circuit
	FOR( i, 0, 25 )
	if( enable[i] && abs(indeg[i]-outdeg[i])>1 )
	return false;
	int cnt = 0;
	FOR( i, 0, 25 )
	if( enable[i] && (indeg[i]!=outdeg[i]) ) ++cnt;
	return cnt <= 2;
	}
	// main function
	int main( void )
	{
	char buf[1005];
	int u, v;
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d", &n );
	// init
	ecnt = 0;
	clr( ehead, -1 );
	clr( indeg, 0 );
	clr( outdeg, 0 );
	clr( enable, false );
	FOR( i, 1, n ) {
	scanf( "%s", buf );
	u = buf[0]-'a';
	v = buf[strlen(buf)-1]-'a';
	addEdge( u, v );
	++outdeg[u];
	++indeg[v];
	enable[u] = enable[v] = true;
	}
	if( check() ) puts("Ordering is possible.");
	else puts("The door cannot be opened.");
	}
	return 0;
	}

view raw 10129 - Play on Words.cpp hosted with ❤ by GitHub