Social Network

题目大意

有$n$个互相不认识的人参加会议,主持人需要介绍$m$,每次介绍会让两个不同的人认识，主持人可以任意介绍两个人

但是需要满足:第$i$次介绍完之后,$x_{1,2…i}$分别于$y_{1,2…i}$认识。

假如$A$认识$B$,$B$认识$C$,那么$A$也就和$C$互相认识了。

对于每次介绍,求出在满足条件的情况下,某个人认识的人最多的数量是多少。（每次介绍单独计算,即 计算“经过$i$次介绍的介绍方法可以和经过$i-1$次介绍的介绍方法不同”）

思路

这种关系显然是要用并查集来表示认识关系的。

那么对于介绍$i$次的情况,对于每一个要满足的条件$x_j,y_j(1\le j \le i)$:

• 如果$x_j,y_j$在不同的并查集,那么我们必须介绍这两个并查集中的人互相认识,那么我们尽量把所有人都介绍给同一个人认识,这样就能满足某个人认识的人最多,而这个人数的数量,其实就是这个并查集的大小

• 如果$x_j,y_j$已经在不同的并查集里了,那么说明我们可以任意介绍两个人,为了满足某个人认识的人最多,那么我们肯定是合并两个最大的并查集。

具体做法

对于每一次回答,我们重新计算并查集,顺带算出可以任意合并次数,然后按照并查集大小,依次合并,计算答案。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 1e4 + 7;

int n, m, fa[maxN], siz[maxN], e[maxN][2], num[maxN];

int Find(int x)
{
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

bool cmp(int x, int y)
{
    return siz[x] > siz[y];
}

int main()
{
    scanf("%d%d", &n, &m);
    int ans = 0;
    for(int i = 1; i <= m; ++i) {
        for(int i = 1; i <= n; ++i) {
            fa[i] = i;
            siz[i] = 1;
            num[i] = i;
        }
        scanf("%d%d", &e[i][0], &e[i][1]);
        int cnt = 0, mx = 0;
        for(int j = 1; j <= i; ++j) {
            int fx = Find(e[j][0]), fy = Find(e[j][1]);
            if(fx != fy) {
                fa[fy] = fx;
                siz[fx] += siz[fy];
                if(siz[fx] > siz[mx])
                    mx = fx; //记录最大的并查集编号
            }
            else
                ++cnt;
        }
        sort(num + 1, num + 1 + n, cmp); //num数组的值就是并查集编号,num[1]表示就是最大的并查集编号
        for(int i = 1; i <= n && cnt; ++i) {
            int fz = Find(num[i]);
            if(fz == mx)
                continue;
            fa[fz] = mx;
            siz[mx] += siz[fz];
            cnt--;
        }
        printf("%d\n", siz[mx] - 1);
    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/12/11/Social-Network/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！