代码还比较易懂,直接贴了
#include<iostream> #include<cstring> using namespace std; struct dictree { struct dictree * child[52]; int num; }*root; int n; int ID; int father[200010]; int rank[200010]; void create(int k); int find(int k); int Union(int a,int b); int update(char *str); void Delete(struct dictree * now); int main() { int t; char str1[25],str2[25]; int t1,t2; while(cin>>t) { while(t--) { ID=0; cin>>n; create(n); root=new struct dictree; root->num=-1; for(int i=0;i<52;i++) root->child[i]=NULL; for(i=0;i<n;i++) { scanf("%s%s",&str1,&str2); t1=update(str1); t2=update(str2); t1=find(t1); t2=find(t2); printf("%d\n",Union(t1,t2)); } } } return 0; } int update(char *str) { struct dictree * now,*newnode; int c; now=root; for(int i=0;i<strlen(str);i++) { if(str[i]>='a' && str[i]<='z') c=str[i]-'a'; else c=str[i]-'A'+26; if(now->child[c]!=NULL) { now=now->child[c]; } else { newnode=new struct dictree; newnode->num=-1; for(int i=0;i<52;i++) { newnode->child[i]=NULL; } now->child[c]=newnode; now=newnode; } } if(now->num==-1) now->num=ID++; return now->num; } void create(int k) { for(int i=0;i<2*k;i++) { father[i]=i; rank[i]=1; } } int find(int k) { if(father[k]!=k) { father[k]=find(father[k]); } else return k; return father[k]; } int Union(int a,int b) { if(a==b) return rank[a]; if(rank[a]>rank[b]) { father[b]=a; rank[a]+=rank[b]; rank[b]=0; return rank[a]; } else { father[a]=b; rank[b]+=rank[a]; rank[a]=0; return rank[b]; } }