| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
遗留了若干月的问题……#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
const int NMax=500000;
struct trie
{
int key;
trie *c[26];
}*Root,pool[5000000];
int nn,L,father[NMax],G[NMax];
int Find(char a[])
{
//int len=strlen(a);
trie *p=Root;
for(int i=0;a[i]!=0;i++)
{
if(!p) {return -1;}
p=p->c[a[i]-'a'];
}
if(!p) {return -1;}
return p->key;
}
int Insert(char a[])
{
//int len=strlen(a);
if(!Root)
{
trie *q=&pool[L++];
q->key=-1;
Root=q;
}
trie *p=Root;
for(int i=0;a[i]!=0;i++)
{
if(p->c[a[i]-'a']==NULL)
{
trie *q=&pool[L++];
q->key=-1;
p->c[a[i]-'a']=q;
}
p=p->c[a[i]-'a'];
}
return (p->key=nn++);
}
int Find(int a)
{
int R,s=a,tmp;
for(R=a;father[R]>=0;R=father[R]);
while(father[s]>=0)
{
tmp=father[s];
father[s]=R;
s=tmp;
}
return R;
}
void Union(int a,int b)
{
int fa=Find(a),fb=Find(b);
if(fa==fb) return ;
father[fa]=fb;
}
int main()
{
nn=0; L=0;
memset(father,-1,sizeof(father));
int tmp,tmp2;
char buf1[15],buf2[15];
bool has=0;
Root=&pool[L++];
while(scanf("%s%s",buf1,buf2)!=EOF)
{
//if(buf1[0]=='#' && buf2[0]=='#') break;
has=1;
//int la=strlen(buf1),lb=strlen(buf2);
tmp=Find(buf1);
if(tmp==-1)
tmp=Insert(buf1);
tmp2=Find(buf2);
if(tmp2==-1)
tmp2=Insert(buf2);
G[tmp]++;
G[tmp2]++;
Union(tmp,tmp2);
}
bool flag=1;
int tot=0;
for(int i=0;i<nn;i++)
{
if(father[i]<0)
{
tot++;
if(tot>1)
{
flag=0;
break;
}
}
}
if(flag)
{
tot=0;
for(int i=0;i<nn;i++)
{
tmp=G[i];
if(tmp%2!=0)
tot++;
}
if(tot!=2&&tot!=0) flag=0;
}
if(flag || !has) puts("Possible");
else puts("Impossible");
getchar(); getchar();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator