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