hdu 3172 Virtual Friends(并查集)University of Waterloo Local Contest 2008.09

时间:2021-08-27 09:51:38

题目比较简单,但作为长久不写题之后的热身题还是不错的。

统计每组朋友的朋友圈的大小。

如果a和b是朋友,这个朋友圈的大小为2,如果b和c也是朋友,那么a和c也是朋友,此时这个朋友圈的大小为3。

输入t,表示接下来有t组数据。

每组数据有n组朋友关系。

接下来n行,每行一组朋友关系,然后输出这组朋友的朋友圈大小,即有多少朋友。

然后又是t组数据……(这点好坑)重复上述输入,直到数据结束。

因为最多有10^5个人,那么如果用线性字符串数组保存人名,肯定超时得不要不要的,所以要用map(每次操作时间复杂度为log2(n))。

据说如果并查集不压缩也会爆。我没试,诸位可以试一下。

废话说完,上代码

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <string>
using namespace std; map<string, int> mp; //字符串与数字转换
int val[]; //朋友数
int mg[]; //并查集使用的数组
int n, t; int find(int x)
{
int fx = x;
while(mg[fx] != fx) fx = mg[fx];
while(mg[x] != x)
{
int mid = mg[x];
mg[x] = fx;
x = mid;
}
//printf("%5d\n", fx);
return fx;
} void merge(int x, int y)
{
int mx = find(x);
int my = find(y);
if(mx != my)
{
val[mx] += val[my];
val[my] = val[mx];
mg[mx] = my; }
printf("%d\n", val[mx]);
} int main()
{
// freopen("test.txt", "r", stdin);
while(~scanf("%d", &t))
{
while(t--)
{
scanf("%d", &n);
for(int i = ; i < ; i++)
{
val[i] = ;
mg[i] = i;
}
char a[], b[];
int ans = ; //因为map中int初始值为0,所以赋值时应从1开始
mp.clear(); //每次注意清空mp
for(int i = ; i < n; i++)
{
scanf("%s%s", a, b);
if(!mp[a]) mp[a] = ans++; //加入新节点
if(!mp[b]) mp[b] = ans++;
merge(mp[a], mp[b]);
}
}
}
return ;
}