学步园

并查集题目

用map映射的代码跑了1100多ms，而采用trie树保存人名的代码仅跑了203ms。

采用map映射

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;
int root[10010],sign[10010];
map<string,int>list;
int find(int c){
	if(root[c]!=c)
		root[c]=find(root[c]);
	return root[c];
}
void check(int a,int b){
	int ra=find(a);
	int rb=find(b);
	if(ra!=rb){
		root[ra]=rb;
		sign[rb]+=sign[ra];
	}
}
int main(){
	string n1,n2;
	int n,m;
	int len;
	while(scanf("%d",&n)!=EOF){
		while(n--){
			list.clear();   //貌似不加这句就WA
			scanf("%d",&m);
			if(m==0){
				printf("0\n");
				continue;
			}
			len=0;
			while(m--){
				cin>>n1>>n2;
				if(list.find(n1)==list.end()){
					root[len]=len;
					sign[len]=1;
					list[n1]=len++;
				}
				if(list.find(n2)==list.end()){
					root[len]=len;
					sign[len]=1;
					list[n2]=len++;
				}
				check(list[n1],list[n2]);
				printf("%d\n",sign[find(list[n1])]);   //输出不能是cout，否则TLE，汗！
			}
		}
	}
	return 0;
}

采用trie树

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int roott[10010],sign[10010];
int len;
struct node{
    node *next[60];
    int flag;
    node(){
        memset(next,NULL,sizeof(next));
        flag=0;
    }
};
int find(int c){
    if(roott[c]!=c)
        roott[c]=find(roott[c]);
    return roott[c];
}
void check(int a,int b){
    int ra=find(a);
    int rb=find(b);
    if(ra!=rb){
        roott[ra]=rb;
        sign[rb]+=sign[ra];
    }
}
int insert(char *cur,node *root){
    node *p=root;
    int i=0;
    while(cur[i]){
        int index=cur[i]-'A';
        if(p->next[index]==NULL)
            p->next[index]=new node();
        p=p->next[index];
        i++;
    }
    if(p->flag!=0)
        return p->flag;
    else{
        p->flag=len;
        return 0;
    }
}
int main(){
    char n1[22],n2[22];
    int n,m;
    while(scanf("%d",&n)!=EOF){
        while(n--){
            node *root=new node;
            scanf("%d",&m);
            if(m==0){
                printf("0\n");
                continue;
            }
            len=1;
            while(m--){
                cin>>n1>>n2;    
                if(insert(n1,root)==0){
                    roott[len]=len;
                    sign[len]=1;
                    len++;
                }
                if(insert(n2,root)==0){
                    roott[len]=len;
                    sign[len]=1;
                    len++;
                }
                //cout<<insert(n1,root)<<insert(n2,root)<<endl;
                check(insert(n1,root),insert(n2,root));
                printf("%d\n",sign[find(insert(n1,root))]);
            }
        }
    }
    return 0;
}