这题是一个很简单额并查集的题目，首先第一步是要用map将字符串映射为整型，这样方便后面的处理，然后就是用一个rank[]数组来记录每个朋友圈的人数。之后就是简单的并查集操作了。
这里给出一组测试案例：
1
6
Fred Barney
Barney Betty
Betty Wilma
AAAAA BBBBB
AAAA BBBBB
AAAA Fred
输出结果应是：
2
3
4
2
3
7
3
4
2
3
7
代码如下：
#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string"
#include"string.h"
#include"cmath"
#include"ctype.h"
#include"map"
#include"vector"
#include"queue"
#include"stack"
using namespace std;
const int mx=;
int num_nest;
int F;
map<string,int>name;
int fa[*mx];
int Rank[*mx]; void Set()
{
for(int i=;i<*F;i++)
{
fa[i]=i;
Rank[i]=;
}
} int Find(int x)
{
int t1,t2=x;
while(t2!=fa[t2]) t2=fa[t2];
while(x!=t2)//可以减小时间复杂度
{
t1=fa[x];
fa[x]=t2;
x=t1;
}
return t2;
} void Union(int x,int y)
{
int fx=Find(x);
int fy=Find(y);
if(fx!=fy)
{
fa[fx]=fy;
Rank[fy]+=Rank[fx];
Rank[fx]=Rank[fy]; }
} bool is_exist(const string &str)//查找map中是否已存在该元素
{
return name.find(str)== name.end();
} void IO()
{
while(scanf("%d",&num_nest)==)
{
while(num_nest--)
{
string name1,name2;
int cnt=,id1,id2;
name.clear();
scanf("%d",&F);
Set();
getchar();
while(F--)
{
cin>>name1;
if(is_exist(name1))
{
name.insert(pair<string,int>(name1,cnt));
id1=cnt;
cnt++;
}
else
id1=(name.find(name1))->second;
cin>>name2;
if(is_exist(name2))
{
name.insert(pair<string,int>(name2,cnt));
id2=cnt;
cnt++;
}
else
id2=(name.find(name2))->second;
Union(id1,id2);
int fid1=Find(id1);
printf("%d\n",Rank[fid1]);
}
}
}
}
int main()
{
IO();
return ;
}