> #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;
> }

• Re:做过的人帮忙找原因，代码很容易看懂！！！ (356) sunmoonstar 2008-08-04 18:10:59