hdu3172 Virtual Friends

水题，边合并边输出就行了，所以可以在merge里面输出比较方便

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

map<string,int> f;
int r[100005],vis[100005];

int root(int a)
{
    if(r[a]==a) return a;
    else return r[a]=root(r[a]);
}

void merge(int a,int b)
{
    int ra,rb;
    ra=root(a);
    rb=root(b);
    if(ra==rb)
    {
        printf("%d\n",vis[ra]);
    }
    else if(ra<rb)
    {
        r[rb]=ra;
        vis[ra]+=vis[rb];
        printf("%d\n",vis[ra]);
    }
    else
    {
        r[ra]=rb;
        vis[rb]+=vis[ra];
        printf("%d\n",vis[rb]);
    }
}

int main()
{
    char a[25],b[25];
    int t,i,n,cnt;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            f.clear();
            scanf("%d",&n);
            for(i=1;i<=100001;i++)
                r[i]=i,vis[i]=1;
            cnt=1;
            for(i=0;i<n;i++)
            {
                scanf("%s%s",a,b);
                if(!f[a])
                    f[a]=cnt++;
                if(!f[b])
                    f[b]=cnt++;
                merge(f[a],f[b]);
            }
        }
    }

    return 0;
}

hdu3172 Virtual Friends,布布扣,bubuko.com

hdu3172 Virtual Friends

原文：http://blog.csdn.net/u011032846/article/details/20940019