2513.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <memory.h>
using namespace std;
char word[500010][20];
char *w[500010];
int begin[500010];
int end[500010];
bool sign[500010];
struct edge
{
	char *a,*b;

}e[500010];
int n, m;
bool cmp( char *a, char *b )
{
	return strcmp( a, b ) < 0;
}
bool cmp2( char *a, char *b )
{
	return strcmp( a, b ) == 0;
}
bool cmp1( edge a, edge b )
{
	return strcmp( a.a, b.a ) < 0;
}
void init()
{
	int i=0, j, k;
	while( scanf( "%s %s", word[i], word[i+1] ) == 2 )
	{
		w[i] = word[i];
		w[i+1] = word[i+1];		
		e[i].a = word[i];
		e[i].b = word[i+1];		
		e[i+1].a = word[i+1];
		e[i+1].b = word[i];
		i+=2;
	}
	n = i;
	sort( w, w+n, cmp );
	m = unique_copy( w, w+n, w, cmp2 ) - w;
	sort( e, e+n, cmp1 );	
	begin[0] = 0;
	for( k=0,j=0,i=1; j<n&&i<n ; i++ )
	{
		while( i < n && strcmp( e[i].a, e[j].a ) == 0 )
				i++;
		end[k++] = i;
		if( i < n )begin[k] = i;
		j = i;
	}
	if( j < n ) 
	 end[k++] = n;
	if( k!=m )while(1)printf("ok\n");
	memset( sign, 0, sizeof( sign ) );

}
int reach;
void find( int a)
{
	int i, j;
	sign[a] = true;
	reach++;

	for( i=begin[a]; i<end[a]; i++ )
	{
		j = std::lower_bound( w, w+m, e[i].b, cmp ) - w;
	
		if( !sign[j] )	find( j );
	}
}
int main()
{
	int i, odd;
	init();

	odd = 0;
	for( i=0; i<m&&odd<=2; i++ )
	{
		if( ( ( end[i] - begin[i] ) & 1 ) == 1 )
			odd++;
	}
	if( odd != 2 && odd != 0 )
	{
		printf( "Impossible\n" );
	}
	else
	{
		reach = 0;
		if( m ) find( 0 );

		if( m == 0 || reach == m )
			printf( "Possible\n" );
		else printf( "Impossible\n" );
	}
	return 0;
}