#include <cstdio>
#include <memory.h>

const int maxn = 500010;

struct node
{
	int n;
	node *next[26];

	node()
	{
		n = -1;
		memset( next, 0, sizeof(next) );
	}
};

node *head = new node;
int num = 0;
int sum[maxn], fa[maxn];

int creat_dic( char *s )
{
	node *p = head;
	int i, k;

	for ( i = 0; s[i] - '\0'; ++i )
	{
		k = s[i] - 'a';
		if ( p->next[k] == 0 )
			p->next[k] = new node;

		p = p->next[k];
	}

	if ( p->n == -1 )
		p->n = num++;

	return p->n;
}

bool pd1()
{
	for ( int i = 0; i < num; ++i )
		if ( fa[i] - fa[0] )
			return 0;
	
	return 1;
}

bool pd2()
{
	int k = 0;
	for ( int i = 0; i < num; ++i )
		if ( sum[i] % 2 )
			k++;

	if ( k > 2 )
		return 0;
	else
		return 1;
}

int main()
{
	int i, u, v;
	char s1[15], s2[15];

	memset( sum, 0, sizeof(sum) );
	for ( i = 0; i < maxn; ++i )
		fa[i] = i;

	while ( scanf("%s %s", &s1, &s2) != EOF )
	{
		u = creat_dic(s1);
		v = creat_dic(s2);

		sum[u]++;  sum[v]++;

                //一时脑热，这样写了，没用并查集，居然过了
		if ( fa[u] < fa[v] )
		    fa[v] = fa[u];
		else
			fa[u] = fa[v]; 
	}

	if ( pd1() && pd2() )
		printf("Possible\n");
	else
		printf("Impossible\n");

	return 0;
}

• Re:测试数据有漏洞··· (1423) scut_lf 2011-03-10 16:27:53
• Re:测试数据有漏洞··· (26) scut_lf 2011-03-10 16:28:16