4780036_ac_1313ms_69516k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 76 行

#include<stdlib.h>
#include<iostream>
using namespace std;
struct node
{
	node *child[26];
	int num;
	node * father;
};
node *root;
int result;
int father_num;
char x1[12],x2[12];
void trie()
{
	root=new node();
	int i;
	root->num=0;
	root->father=NULL;
	for(i=0;i<26;i++)
	{
		root->child[i]=NULL;
	}
}
node * ts(char x[])
{
	int i=0;
	node *r=root;
	while(x[i])
	{
		if(r->child[x[i]-'a']==NULL)
		{
			node *p=new node();
			int j;
			for(j=0;j<26;j++)
			{
				p->child[j]=NULL;
			}
			p->num=0;
			p->father=NULL;
			r->child[x[i]-'a']=p;
		}
		r=r->child[x[i]-'a'];
		i++;
	}
	r->num++;
	if(r->num==1) father_num++;
	if(r->num%2==1) result++;
	else result--;
	return r;
}
node *find_f(node * x)
{
	node *p=x;
	while(p->father) p=p->father;
	while(x->father) {node *q=x;x=x->father;q->father=p;}//压缩路径
	return p;
}
int main()
{
	trie();
	result=0;
	father_num=0;
	while(scanf("%s%s",x1,x2)!=EOF)
	{
		node *r1=ts(x1);
		node *r2=ts(x2);
		node * f1=find_f(r1);
		node * f2=find_f(r2);
		if(f1!=f2) {f2->father=f1;father_num--;}
	}
	if(father_num>1) cout<<"Impossible"<<endl;
	else if(result==2||result==0) cout<<"Possible"<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}