Information Sharing zoj3641 并查集

Description

There is going to be a test in the kindergarten. Since the kids would cry if they get a low score in the test, the teacher has already told every kid some information about the test in advance.

But the kids are not satisfied with the information teacher gave. They want to get more. On the testing day, some kids arrived to the classroom early enough, and then shared his/her information with another. kids are honest, if A shares with B, B can get all the information A knows, so does A.

At first the classroom is empty. As time pass by, a kid would arrive, or share information with other. However, the teacher hides somewhere, watching everything. She wants to know how much information some kid has gotten.

Input

There are multiple cases.

The first line of each case contains an integer n, indicating there is n actions.

The following n actions contain 3 types.

1: “arrive Namema1a2 ..am”, means the kid called Name arrives at the classroom. He has m information, their id is a1a2 …am.

2: “share Name1Name2”, means that the kids called Name1 and Name2 share their information. (The sharing state will keep on, that means, if A share with B, later B share with C, A can also get all C’s information via B. One kid may share with himself, but it doesn’t mean anything.)

3: “check Name”, means teacher wants to know the number of information kid called Name has got.

n is less than 100000, and is positive. The information id is among [0,1000000].

Each Name has at most 15 characters.

There would appears at most 1000 distinct information.

Each kid carry no more than 10 information when arriving(10 is included).

Output

For every “check” statement, output a single number. If there’s no check statement, don’t output anything.

Sample Input

8

arrive FatSheep 3 4 7 5

arrive riversouther 2 4 1

share FatSheep riversouther

check FatSheep

arrive delta 2 10 4

check delta

share delta FatSheep

check riversouther

Sample Output

425

Hint

check 1: FatSheep has 1 4 5 7, having all the information. So answer is 4.

check 2: delta has only 4 10 , doesn’t have 1 5 7. So answer is 2

check 3: riversouther has 1 4 5 7 10, having all the information. So answer is 5

（1）題意：給出n個操作，操作有的三種：

①添加一個人，這個人攜帶了一些資訊。

②分享某兩個人的資訊。

③查詢某個人所擁有的不同的資訊的個數。

輸出每次查詢一個人時他手裡的資訊個數。

（2）解法：其實就是個并查集，用個set來記錄每個人所擁有的資訊，當兩個人分享資訊時，将這兩個人合并，把一個人的資訊都添加到另一個人上面，然後把這個擁有的資訊删除。注意：若A與B分享後，B在與C分享。此時A也知道了C的資訊。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
int pa[];
set<int>you[]; //第幾個擁有的數字
set<int>:: iterator it;
map<string,int>mp;
char str[],name1[],name2[];
int Find(int x)
{
    if(x==pa[x]) return x;
    int y=Find(pa[x]);
    it=you[x].begin();
    while(it!=you[x].end())
    {
        int val=*it;
        ++it;
        if(you[y].count(val)) continue;
        you[y].insert(val);
    }
    you[x].clear();
    return pa[x]=y;
}
void Uion(int x,int y)
{
    int a=Find(x);
    int b=Find(y);
    if(a!=b)
    {
        pa[b]=a;
        Find(b);
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        mp.clear(); //清空map
        int cnt=;
        while(n--)
        {
            scanf("%s",str);
            if(strcmp(str,"arrive")==)
            {
                scanf("%s",name1);
                mp[string(name1)]=++cnt;  //把名字對應為一個數字
                you[cnt].clear();  //把他擁有的set清空
                pa[cnt]=cnt;
                int m,v;
                scanf("%d",&m);
                while(m--)
                {
                    scanf("%d",&v);
                    you[cnt].insert(v);  //把輸入的數字全部加到you[cnt]的set中
                }
            }
            else if(strcmp(str,"share")==)
            {
                scanf("%s%s",name1,name2);
                int x=mp[string(name1)];  //對應的數字
                int y=mp[string(name2)];
                Uion(x,y);
            }
            else
            {
                scanf("%s",name1);
                int x=Find(mp[string(name1)]);
                printf("%d\n",you[x].size());  //把擁有的容器中的個數讀出來
            }
        }
    }
    return ;
}