> //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 (0) flymouse 2007-07-24 14:15:47
• TLE啊 (0) flymouse 2007-07-24 14:15:59