#include<stdio.h>
#include<iostream>
using namespace std;

#define VERTEX_NUM	1000

int color[VERTEX_NUM],set[VERTEX_NUM];
int Hash(char * str)
{
	int hash = 1;
	while(*str)
		hash = (hash*29 + *str++ - 'a')%VERTEX_NUM;
	return hash;
}
int find_set(int x)
{
	int tmp=0;
	int root=x;
	while(set[root]>=0)
	{
		root=set[root];
	}
	while(x!=root)
	{
		tmp=set[x];
		set[x]=root;
		x=tmp;
	}
	return root;
}
void union_set(int root1,int root2)
{
	int sum = set[root1]+set[root2];
	if(set[root1]>set[root2])
	{
		set[root1] = root2;
		set[root2] = sum;
	}
	else
	{
		set[root2] = root1;
		set[root1] = sum;
	}
}
int main()
{
	int n1,n2,n=0,root1,root2,i,no=0;
	char a[11],b[11];
	for(i=0;i<VERTEX_NUM;++i)
	{
		set[i]=-1;
		color[i]=0;
	}
	while(scanf("%s%s",a,b)!=EOF)
	{
		++n;
		n1=Hash(a);
		n2=Hash(b);
		++color[n1];
		++color[n2];
		root1=find_set(n1);
		root2=find_set(n2);
		if(root1!=root2)
			union_set(root1,root2);
	}
	int root=1;
	for(int i=0;i<VERTEX_NUM;++i)
	{
		if(color[i]>0)
		{
			if(color[i]%2)
			{
				++no;
				if(no>2)
				{
					printf("Impossible\n");
					return 0;
				}
			}
			if(root==1)
				root = find_set(i);
			else
				if(root!=find_set(i)){ printf ("Impossible\n");return 0;}
		}
	}
	printf("Possible\n");
	return 0;
}

• Re:为什么这样的hash能AC，数组才1000居然AC了，谁能解释解释 (20) ICLiuLi 2017-08-04 19:35:32