职务地址：

pid=3172">HDU 3172

带权并查集水题。每次合并的时候维护一下权值。注意坑爹的输入。

。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define LL long long

int bin[210000], num[210000];

int find1(int x)

{

    return bin[x]==x?

x:bin[x]=find1(bin[x]);

}

void join(int x, int y)

{

    int f1=find1(x);

    int f2=find1(y);

    if(f1!=f2)

    {

        bin[f2]=f1;

        num[f1]+=num[f2];

        printf("%d\n",num[f1]);

    }

    else

        printf("%d\n",num[f2]);

}

int main()

{

    int t, n, i, cnt;

    char s1[30], s2[30];

    map<string,int>q;

    while(scanf("%d",&t)!=EOF)

    {

        while(t--)

        {

            scanf("%d",&n);

            for(i=1; i<210000; i++)

            {

                bin[i]=i;

                num[i]=1;

            }

            q.clear();

            cnt=1;

            while(n--)

            {

                getchar();

                scanf("%s%s",s1,s2);

                if(!q[s1])

                    q[s1]=cnt++;

                if(!q[s2])

                    q[s2]=cnt++;

                join(q[s1],q[s2]);

            }

        }

    }

    return 0;

}