poj 2513(字典树等部分借鉴网上代码)

#include <iostream> #include<string> #include<iomanip> #include<cstdlib> #include<string.h> #include<malloc.h> using namespace std; int color=0; int ans[500010]; int deg[500010]={0}; class Tritree { public: int id; bool isword; Tritree *next[26]; Tritree() { int i; isword=false; memset(next,0,sizeof(next)); } }root; int insert(char *str) { int i,j=0,md; Tritree *p=&root,*q; for(i=0;i<strlen(str);i++) { md=str[i]-'a'; if(p->next[md]==NULL) { q=new Tritree; p->next[md]=q; p=p->next[md]; } else p=p->next[md]; if(i==strlen(str)-1) { if(!p->isword) { p->isword=true; p->id=color++; } } } return p->id; } void unTritree() { for(int i=0;i<26;i++) if(root.next[i]!=NULL) free(root.next[i]); } int find(int m) { if(ans[m]!=m) ans[m]=find(ans[m]); return ans[m]; } void hand(int a,int b) { int i,j; i=find(a); j=find(b); ans[i]=j; } int main() { int i,j,re,num=0; char a[11],b[11]; for(i=0;i<500010;i++) ans[i]=i; while(cin>>a>>b) { i=insert(a);deg[i]++; j=insert(b);deg[j]++; hand(i,j); } re=find(0); for(i=0;i<color;i++) { if(find(i)!=re) { cout<<"Impossible"<<endl; unTritree(); return 0; } } for(i=0;i<color;i++) { if(deg[i]%2) num++; } if(num==0||num==2) cout<<"Possible"<<endl; else cout<<"Impossible"<<endl; unTritree(); return 0; }