|
这是一道简单的并查集题目，对于每个人，都先建一棵以他为根的根树，用数组实现树的思想，只要一个fa[]数组就够了，
然后写一个寻找树根的函数，因为我们每次操作都是对树根进行的，再写一个判断函数，判断在同一棵树中的时候，
返回1，不在同一棵树的时候，把层数小的并到层数大的树中，返回0，另外一个数组，保存以每个人为根的朋友数。
就这样了，TLE!(不听老人言，用cin没用scanf) CE!(点了C提交) AC!(换回C++提交)
#include
#include
const int maxn = 100000 + 10; //最多可能有100000个人
int fa[maxn], cnt[maxn], height[maxn]; //fa[i]为i的朋友，就是树的结点的父亲，cnt[i]为以i为根的朋友数，height[i]为i为根的树的层数
int find(int x) //寻找x的根，朋友中的老大！！！
{
while(fa[x] != x)
{
x = fa[x];
}
return x;
}
int judge(int x, int y) //判断x与y的关系
{
int xx = find(x);
int yy = find(y);
if(xx == yy) //如果x与y已在同一棵树中，返回1
return 1;
else //如果x与y不在同一棵树中
{
if(height[xx] > height[yy]) //当x所在的树的高度>y所在的树的高度时
{
fa[yy] = xx;
cnt[xx] += cnt[yy];
}
else if(height[xx] == height[yy]) //当x所在的树的高度==y所在的树的高度时
{
fa[yy] = xx;
cnt[xx] += cnt[yy];
height[xx]++;
}
else //当x所在的树的高度 |