[并查集+set]zoj 3641：Information Sharing

大致题意：
    有三种操作  arrive用来表示某人知道的信息；share用来表示 两个人互相交流信息；check操作的时候，输出这个人知道的信息数量，操作的数量小于100000.

 

大致思路：

    并查集+set去重。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<set>
using namespace std;
const int nMax=1000005;
int n,father[nMax],rank[nMax],N,M,num[nMax],sum;   //rank近似树的高度。

int cnt,n1;
set<int>sset[nMax];

map<string,int>map1;
int getnum(string x){
    if (map1.find(x)==map1.end()){
        map1.insert(make_pair(x,cnt));
        cnt++;
        return cnt-1;
    }else return map1[x];
}

int find(int x){ // 寻找父节点
    if(x!=father[x])
        return father[x]=find(father[x]);
    return x;
}

void setunit(int x,int y)
{
     set<int>::iterator iter;
     for (iter = sset[x].begin(); iter != sset[x].end(); iter++)
     {
         sset[y].insert(*iter);
     }
//     sset[x].clear();
}

void unite(int a,int b){
    int x=find(a);
    int y=find(b);
    if(x==y)
        return ;
    else{
        if(rank[x]>rank[y]){
            father[y]=x;
            setunit(y,x);
        }
        else if(rank[x]<rank[y]){
            father[x]=y;
            setunit(x,y);
        }
        else{
            father[x]=y;
            setunit(x,y);
            rank[y]++;
        }
    }
}

void init(){    // 初始化
    int i;
    for(i=0; i<nMax-1; i++){
        father[i]=i;
        rank[i]=0;
    }
    n=0;
    sum=N;
}

int main(){
	int num,a,b,c,d,i,j,k;
	while(cin>>num){
	    map1.clear();
	    for(i=1;i<=nMax;i++)sset[i].clear();
		init();
		cnt=1;
		char act[50];
		string name;
		while(num--){
			cin>>act;
			if(act[0]=='a'){
			    cin>>name;
			    cin>>a;
			    b=getnum(name);
			    for(i=0;i<a;i++)
			    {
			        cin>>c;
			        sset[b].insert(c);
			    }
				continue;
			}
			if(act[0]=='s'){
			    cin>>name;
			    b=getnum(name);
			    cin>>name;
			    c=getnum(name);
			    unite(b,c);
				continue;
			}
			if(act[0]=='c'){
			    cin>>name;
			    b=getnum(name);
			    cout<<sset[find(b)].size()<<endl;
			}
		}
	}
	return 0;
}