/***************************************
题目分析：POJ2513
	先判断连通性（使用Union_Set）
	再判断结点的度（用degree[]记录）
****************************************/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
 
using namespace std;

#define REP(i,N) for(int i=0;i<N;i++)
#define REPV(i,ar) for(int i=0;i<ar.size();i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define EACH(it,mp) for(__typeof(mp.begin()) it=mp.begin();it!=mp.end();it++)
#define sz size()
#define pb push_back
typedef vector<int> VI;
typedef vector<string> VS;
typedef __int64 ll;
//data
int degree[ 500010 ] = { 0 };
int uset[ 500010 ] = { -1 };
int col_num = 0;
class Num{
public:
	int index;
	Num* p[ 26 ];
public:
	Num()
	{
		index = -1;
		FOR( i, 0, 25 ) p[ i ] = NULL;
	}
};

Num* ROOT;

int GetNum( char * str )
{
	int num;
	Num* P = ROOT;
	FOR( i, 0, strlen( str ) - 1 )
	{
		int index = str[ i ] - 'a';
		if( P->p[ index ] == NULL )
		{
			P->p[ index ] = new Num();
		}
		P = P->p[ index ];
	}
	if( P->index == -1 ) P->index = col_num++;
	return P->index;
}

int uset_find( int inode )
{
	if( uset[ inode ] < 0 ) return inode;
	int j = inode;
	while( uset[ j ] >= 0 )
	{
		j = uset[ j ];
	}
	uset[ inode ] = j;
	return j;
}

int uset_union( int r1, int r2 )
{
	if( r1 == r2 ) return 0;
	if( uset[ r1 ] > uset[ r2 ] ) swap( r1, r2 );
	uset[ r1 ] += uset[ r2 ];
	uset[ r2 ] = r1;
	return 0;
}

bool odd( int n )
{
	return n % 2;
}

int main()
{
	ROOT = new Num();
	memset( uset, -1, sizeof( uset ) );
	memset( degree, 0, sizeof( degree ) );
	char color1[ 20 ];
	char color2[ 20 ];
	col_num = 0;
	while( scanf( "%s%s", color1, color2 ) != EOF ){
		int i = GetNum( color1 );//获取颜色编号 O(1)
		int j = GetNum( color2 );//O(1)
		++degree[ i ];
		++degree[ j ];//记录度数	
		uset_union( uset_find( i ), uset_find( j ) ); 
	}//while
	if( uset[ uset_find( 0 ) ] + col_num != 0 )
	{
		printf( "Impossible\n" );
		return 0;
	}
	int odd_num = count_if( degree, degree + col_num, odd );
	if( odd_num <= 2 )
		printf( "Possible\n" );
	else
		printf( "Impossible\n" );
	return 0;
}

• 如果输入数据是空的，你应该输出Impossible (19) xfxyjwf 2008-01-04 08:53:21
  • Re:如果输入数据是空的，你应该输出Impossible (17) andy_lee 2008-01-04 09:20:25
  • 嗯，我就栽在这上面。 (0) instinct 2008-01-04 11:47:27
  • Re:如果输入数据是空的，你应该输出Impossible (20) andy_lee 2008-01-04 11:48:50
    • ……我错了 (0) xfxyjwf 2008-01-04 11:51:10
      • Re:……我错了 (410) andy_lee 2008-01-05 21:01:36
  • Re:如果输入数据是空的，你应该输出Impossible (13) erps 2008-07-17 19:10:36
  • Re:如果输入数据是空的，你应该输出Impossible (4) ljl08 2008-08-02 09:21:21
  • 您老误导人啊 贡献1W (23) nowater 2009-05-15 22:05:57
  • Re:如果输入数据是空的，你应该输出Impossible (17) asuran 2009-10-10 03:51:55