pku2513.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 510000

typedef long long LLN;

typedef struct hashNode
{
	LLN color;
	int cnt;
	int next;
} hashNode;

hashNode hashTable[size * 2];
int NextPos;
int f[size * 2];

int hashCode(char *p)
{
	int h;
	for (h = 0; *p; p++)
		h = (h * 31 + *p) % (size - 19);
	return h;
}

LLN s2n(char *p)
{
	LLN ans = 0;
	for (; *p; p++)
		ans = ans * 31 + (*p - 'a' + 1);
	return ans;
}

int root(int p)
{
	return f[p] == -1 ? p : (f[p] = root(f[p]));
}

int InsertToHashTable(char *s)
{
	LLN v = s2n(s);
	int hv = hashCode(s);
	if (hashTable[hv].color == v)
	{
		hashTable[hv].cnt++;
		return hv;
	}
	if (hashTable[hv].cnt == 0)
	{
		hashTable[hv].color = v;
		hashTable[hv].cnt++;
		return hv;
	}
	else
	{
		while (hashTable[hv].next)
		{
			if (hashTable[hv].color == v)
			{
				hashTable[hv].cnt++;
				return hv;
			}
			hv = hashTable[hv].next;
		}
		hashTable[hv].next = NextPos;
		hashTable[NextPos].color = v;
		hashTable[NextPos].cnt = 1;
		v = NextPos;
		NextPos++;
		return hv;
	}
}

int main()
{
	char s1[11], s2[11];
	NextPos = size;
	int ct, p1, p2, h1, h2, i, rt, res;
	memset(hashTable, 0, sizeof(hashTable));
	memset(f, -1, sizeof(f));
	while (EOF != scanf("%s%s", s1, s2))
	{
		p1 = InsertToHashTable(s1);
		p2 = InsertToHashTable(s2);
		h1 = root(p1);
		h2 = root(p2);
		if (h1 != h2)
			f[h2] = h1;
	}
	rt = -2;
	res = 1;
	ct = 0;
	for (i = 0; i < NextPos; i++)
	{
		if (hashTable[i].cnt)
		{
			if (rt == -2)
				rt = root(i);
			if (root(i) != rt)
			{
				res = 0;
				break;
			}
		}
		if (hashTable[i].cnt % 2)
		{
			ct++;
			if(ct > 2)
			{
				res = 0;
				break;
			}
		}
	}
	printf("%s\n", res ? "Possible":"Impossible");
	return 0;
}