2718616_ac_1322ms_118560k.cc

北大大牛代码 1240道题的原代码 超级权威

//Trie Tree
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX 500001

using namespace std;

queue <int> que;

int no = 0, tmp, num = 0;
vector <int> tree[MAX];
short int visited[MAX];
int din[MAX];
int trie[MAX][26], it, id[MAX][26];

void insert(int t,char str[],int &n)
{
	if (trie[t][str[0]-'a']==-1)
	{
		trie[t][str[0]-'a'] = it++;
		if (str[1]=='\0')
			n = no++, id[t][str[0]-'a'] = n;
		else
			insert(it-1,&str[1],n);
	}
	else
	{
		if (str[1]=='\0')
			n = id[t][str[0]-'a'];
		else
			insert(trie[t][str[0]-'a'],&str[1],n);
	}
}

void bfs()
{
	int i, t;

	que.push(0);
	while (!que.empty())
	{
		t = que.front();
		num++;
		visited[t] = 1;
		que.pop();
		for (i = 0; i < tree[t].size(); i++)
		{
			if (!visited[tree[t][i]])
			{
				visited[tree[t][i]]  = 1;
				que.push(tree[t][i]);
			}
		}
	}
}

int main()
{
	char a[13], b[13];
	int l, r, i;
	int input = 1;

//	freopen("H.0.dat","r",stdin);
	memset(visited,0,sizeof(visited));
	memset(din,0,sizeof(din));
	memset(trie,-1,sizeof(trie));
	it = 1;
	while (scanf("%s%s",a,b)==2)
	{
		input = 0;
		insert(0,a,l);
		insert(0,b,r);
		tree[l].push_back(r);
		tree[r].push_back(l);
		din[r]++;din[l]++;
	}
	if (input)
	{
		printf("Possible\n");
		return 0;
	}
	bfs();
	if (num!=no)
	{
		printf("Impossible\n");
		return 0;
	}
	num = 0;
	int f1, f2;
	f1 = f2 = 1;
	for (i = 0; i < no; i++)
	{
		if (din[i]%2)
		{
			num++;
		}
	}
	if(num==0||num==2)
		printf("Possible\n");
	else
		printf("Impossible\n");
	return 0;
}