#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

map<string,int> MM;

int In[500010];
int Father[500010];
int rank[500010];
int T = 0;

void Init()
{
	for(int i = 0; i< 500010; ++i) 
	{
		Father[i] = i;
		rank[i] = 0;
		In[i] = 0;
	}
}

int find(int x)
{
	if(x == Father[x]) return x;
	Father[x] = find(Father[x]);
	return Father[x];
}

void Union(int x,int y)
{
	int rootx = find(x);
	int rooty = find(y);
	if(rootx == rooty) return ;
	if(rank[x]>rank[y]) Father[y] = x;
	else {
		Father[x] = y;
		if(rank[x] == rank[y]) rank[x]++;
	}
}

int getnum(char *p)
{
	string s = p;
	map<string,int>::iterator it=MM.find(s);
	if(it == MM.end())
	{
		MM[s] = T++;
		return T-1;
	}
	return it->second;
}

int main()
{
	MM.clear();
	char c1[20],c2[20];
	Init();
	map<string,int>::iterator it1,it2;
	int sh,se;
	while(scanf("%s %s",c1,c2)!=EOF)
	{
		sh = getnum(c1);
		se = getnum(c2);
		In[sh] ++;
		In[se] ++;
		Union(find(sh),find(se));
	}
	if(T==0) {printf("Possible\n");return 0;}
	int cnt = 0;
	for(int i = 0; i< T; ++i)
	{
		if(In[i]%2==1) cnt ++;
	}
	if(cnt!=0&&cnt!=2)
	{
		printf("Impossible\n");
		return 0;
	}
	
	int rot = find(0);
	for(int i = 1; i< T; ++i)
	{
		if(find(i) != rot) {printf("Impossible\n");return 0;}
	}
	printf("Possible\n");
	return 0;
}

• 做过的人帮忙找原因，代码很容易看懂！！！ (1573) caizhicong0503 2008-08-04 17:47:32
  • Re:做过的人帮忙找原因，代码很容易看懂！！！ (356) sunmoonstar 2008-08-04 18:10:59
• Re:大家帮忙看看，Map+并查为什么超时？？？ (53) sunmoonstar 2008-08-04 18:11:47
  • 但我同学有用string过的，时间是3600ms左右，而且他是用Map+dfs（dfs用来判连通) (153) caizhicong0503 2008-08-04 20:06:56
    • 我自己试过，我如果把前面的MAP用字母树来替换的话，就可以过了，这说明的我并查应该没问题！ (98) caizhicong0503 2008-08-04 20:09:45
• Re:我反正用了map/hash_map ，自己写的hash，都没过。可java的map都能过 (0) tzkq 2008-12-16 21:26:17
  • Java三倍时限 (0) Sempr 2008-12-16 21:30:50
    • 我看不止三倍 关键java的类库效率不比c++的慢多少 时间大概在3：2左右 (0) tzkq 2008-12-16 22:52:56
• 哈，突然发现自己的贴被顶出来了，自己再顶下：） (1792) BrainDeveloper 2008-12-16 22:59:37