【Codeforces】1609D Social Network 题解

题目大意

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

但是需要满足：第 $i$ 次介绍完之后，$x_{1,2,\ldots,i}$ 分别与 $y_{1,2,\ldots,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;
}