题意：人与人交友构成关系网，两个人交友，相当于两个朋友圈的合并，问每个出两人，他们目前所在的关系网中的人数。
分析：用并查集，其实就是求每个集合当前的人数。对于人名的处理用到了字典树。
注意：1、题目给出的n是指n对关系，上限有2*n个人。
2、题目很没有意思的既说了有多组数据，又要求输入组数。实际上还是多组数据。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int MAXN=; struct Node{
int c;
Node *child[];
Node(){
c=;
for(int i=;i<;i++)
child[i]=NULL;
}
}*root; int cnt;
int p[MAXN],num[MAXN];
char str1[],str2[]; void init(int n)
{
root=new Node();//
cnt=; for(int i=;i<n;i++)
{
p[i]=i;
num[i]=;
}
} int ID(char str[])
{
Node *p=root;
int len=strlen(str);
for(int i=,k;i<len;i++,p=p->child[k])
{
if(str[i]>='a'&&str[i]<='z')
k=str[i]-'a';
else
k=str[i]-'A'+;
if(p->child[k]==NULL)
p->child[k]=new Node();
}
if(p->c)
return p->c;
return p->c=++cnt;//
} int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
} int main()
{
int T,n;
while(~scanf("%d",&T))
{
while(T--)
{
scanf("%d",&n); init(n*);//
for(int i=;i<n;i++)
{
scanf("%s%s",str1,str2);
int u=ID(str1);
int v=ID(str2); int fu=find(u);
int fv=find(v); if(fu==fv)
printf("%d\n",num[fu]);
else {
p[fv]=fu;
num[fu]+=num[fv];
printf("%d\n",num[fu]);
} }
}
}
return ;
}