[UVa] 10054 - The Necklace

題目網址: http://goo.gl/3j8vzi

題意: 有散落的一堆珠子，每顆珠子都有兩種顏色，想要把這些珠子串成一條項鍊，且滿足相鄰的兩顆珠子必須以相同的顏色相鄰相連，問是否能串成項鍊。



解法: 是否能串成項鍊跟一筆畫很像，很明顯就是問圖是否存在 Eulerian circuit ，但是並不是直接將珠子當成點，顏色當成邊，而是反過來將顏色當成點，珠子的兩個顏色當成邊，然後檢查是否存在 Eulerian circuit ，且使用DFS輸出結果。

連通的無向圖 是歐拉環（存在歐拉迴路）的充要條件是：中每個頂點的度都是偶數。

TAG: Eulerian circuit, DFS

注意:

程式碼:

	/**
	* Tittle: 10054 - The Necklace
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/10
	* File: 10054 - The Necklace.cpp - solve it
	*/
	// 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 1005
	#define M 60
	class Edge {
	public:
	int v, nxt;
	Edge( int _v=0, int _nxt=-1 ): v(_v), nxt(_nxt) {}
	};
	// declarations
	int t;
	int n;
	int ecnt;
	Edge edge[N*2];
	bool enable[M];
	int head[M];
	int cnt[M];
	// functions
	void addedge( int u, int v )
	{
	edge[ecnt] = Edge( v, head[u] );
	head[u] = ecnt++;
	edge[ecnt] = Edge( u, head[v] );
	head[v] = ecnt++;
	}
	int path[N*2];
	int pcnt;
	bool evis[N*2];
	bool vis[M];
	void dfs( int u )
	{
	int v, ne;
	vis[u] = true;
	for( ne=head[u]; ne!=-1; ne=edge[ne].nxt ) if( !evis[ne] ) {
	evis[ne] = evis[ne^1] = true;
	dfs( edge[ne].v );
	}
	path[++pcnt] = u;
	}
	bool check( void )
	{
	static int s;
	FOR( i, 1, 50 ) if( enable[i] && (cnt[i]&1)==1 ) return false;
	pcnt = 0;
	clr( vis, false );
	clr( evis, false );
	for( s=1; s<=50 && !enable[s]; ++s);
	dfs( s );
	FOR( i, 1, 50 ) if( enable[i] && !vis[i] ) return false;
	return true;
	}
	// main function
	int main( void )
	{
	int u, v;
	// input
	scanf( "%d", &t );
	FOR( ti, 1, t ) {
	scanf( "%d", &n );
	// init
	clr( enable, false );
	clr( head, -1 );
	clr( cnt, 0 );
	ecnt = 0;
	FOR( i, 1, n ) {
	scanf( "%d%d", &u, &v );
	enable[u] = enable[v] = true;
	addedge( u, v );
	++cnt[u]; ++cnt[v];
	}
	// solve & output
	if( ti > 1 ) putchar('\n');
	printf( "Case #%d\n", ti );
	if( check() ) {
	FOR( i, 1, pcnt-1 ) printf( "%d %d\n", path[i], path[i+1] );
	} else puts("some beads may be lost");
	}
	return 0;
	}

view raw 10054 - The Necklace.cpp hosted with ❤ by GitHub