做这题主要是为了学习字典树。字典树的作用就是统计不同单词个数(那么就是完成单词与整数的映射关系)。不过字典树的局限性还是很大的，必须保证出现的单词都是小写字母，不能出现数字，下划线，空格之类的字符。
#include<iostream> using namespace std; #define maxn 500005 struct node { int next[26]; int key; }; node trie[maxn]; int cnt[maxn],set[maxn]; int node_index=1,color_key=1; int search(char word[]) { int i=0,temp,p_node=0; while(word[i]!='/0') { temp=word[i]-'a'; if(trie[p_node].next[temp]==NULL) trie[p_node].next[temp]=node_index++; p_node=trie[p_node].next[temp]; i++; } if(trie[p_node].key==0) trie[p_node].key=color_key++; return trie[p_node].key; } void merge(int a,int b) { if(a>b) set[a]=b; else set[b]=a; } int find(int x) { int r=x,i,j; while(r!=set[r]) r=set[r]; i=x; while(i!=r) { j=set[i]; set[i]=r; i=j; } return r; } int main() { char str1[15],str2[15]; int s1,s2,i; memset(cnt,0,sizeof(cnt)); memset(trie,0,sizeof(trie)); for(i=1;i<=maxn;i++) set[i]=i; while(scanf("%s%s",&str1,str2)!=EOF) { s1=search(str1); s2=search(str2); cnt[s1]++; cnt[s2]++; merge(find(s1),find(s2)); } int xx=0,yy=0; for(i=1;i<color_key;i++) { if(find(i)!=1) xx++; if(cnt[i]%2!=0) yy++; } if(xx||(yy!=0&&yy!=2)) printf("Impossible/n"); else printf("Possible/n"); return 0; }
