//2513
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <string>
using namespace std;

char a[11], b[11];
struct Node
{
	Node(const string &str): degree(1), rank(0), p(str){}
	int degree;
	int rank;
	string p;
};

typedef map<string, Node *> Map;
typedef Map::value_type MVT;
typedef Map::iterator Iter;
Map mp;
Iter iter;

void link(const string &x, const string &y)
{
	if(mp[x]->rank > mp[y]->rank)
		mp[y]->p = x;
	else
	{
		mp[x]->p = y;
		if(mp[x]->rank == mp[y]->rank)
			mp[y]->rank++;
	}
}

const string &find_set(const string &x)
{
	if(x != mp[x]->p)
		mp[x]->p = find_set(mp[x]->p);
	return mp[x]->p;
}

void join(const string &x, const string &y)
{
	link(find_set(x), find_set(y));
}

int main()
{
	while(scanf("%s%s", a, b) != EOF)
	{
		if( (iter=mp.find(a)) == mp.end() )
			mp.insert(MVT(a, new Node(a)));
		else
			iter->second->degree++;
		if( (iter=mp.find(b)) == mp.end() )
			mp.insert(MVT(b, new Node(b)));
		else
			iter->second->degree++;

		join(a, b);
	}
	
	iter = mp.begin();
	const string &str = find_set(iter->first);
	iter++;
	for(; iter != mp.end(); iter++)
	{
		if(find_set(iter->first) != str)
		{
			printf("Impossible\n");
			return 0;
		}
	}
	
	int count = 0;
	for(iter = mp.begin(); iter != mp.end(); iter++)
	{
		if(iter->second->degree & 1)
			count++;
	}
	if(count == 0 || count == 2)
		printf("Possible\n");
	else
		printf("Impossible\n");
}

• map 可过, 用G++ 提交试试 (1650) xiaox 2007-03-14 12:15:33
  • map (0) flymouse 2007-07-24 14:15:47
  • TLE啊 (0) flymouse 2007-07-24 14:15:59