原题链接: https://codeforces.com/contest/1609/problem/D

大致题意

给你 $n (2 \le n \le 10^3)$ 个点表示不同的人，和 $d (1 \le d \le n - 1)$ 个限制，每个限制要求两个不同的人 $x$ 和 $y$ 之间存在联系（也就是这两个点在同一个连通块里），一开始任意两点间都不存在边。

你要回答 $d$ 个询问，第 $i$ 个询问要求你添加 $i$ 条边，并满足前 $i$ 个限制，询问的答案是在加完边之后，在所有人中，认识最多人的那个人认识多少人。

$x$ 认识 $y$ 的要求是他俩之间存在直接相连的边，而不是只要存在可达路径，另外值得注意的一点是，每次询问都是独立的，也就是说每次询问都可以看作是从没有边的初始情况开始的，第 $i + 1$ 次询问和第 $i$ 次没有任何关系。

解析

我们可以先考虑如何从最终的图计算答案，而不是先考虑如何构造满足条件的答案图。对于每次询问，我们先随便生成一个满足所有限制的图，这样我们可以得到一些连通块，这些连通块之间是互不干涉的，也就是说我们可以重新分配各个连通块内部的边而依然满足限制，为了让某个人认识尽可能多的人，我们可以从一个连通块里选择一个点，让它和该连通块里的所有其它点直接相连，这样依然满足限制，然后答案就是最大的连通块的大小 $-1$（从样例 1 的图示也可以看出这个结果）。

Explanation of example 1

然后再考虑如何构造答案图。很容易想到的就是每次都将表示限制的边加入图，这样第 $i$ 次生成的图就一定会满足前 $i$ 个限制。但直接这样做会生成冗余的边，假如 $x$ 和 $y$ 已经在一个连通块里了，你再将它们直接连接就没有意义了，还不如再随便连一个不在此连通块里的点，还可以增加这个连通块的大小。所以我们需要改变一下我们的策略，在每次加边的时候判断这两个点有没有相连，如果没有相连就直接连接，如果已经相连，我们就可以在图里的任意两点间连边，我们不妨连接当前图中最大的两个连通块，这样答案就等于这个新合并的最大连通块的大小了。

新生成的连通块 $A$ 现在可能是最大的，但是在后续的连边操作中我们可能会增大其他的连通块，而每个询问又是独立的，所以我们必须将冗余边用来连接每次询问时最大的那几个连通块，而不是一有冗余边就使用它。分析到这里，你应该已经想到怎么写了吧，不妨先停下来理理思路，我们接下来就来讨论如何实现。

实现

我们先初始化一个大小为 $n$ 的并查集，初始时每个点单独构成一个连通块，再初始化一个变量 $cnt = 0$ 记录当前的冗余边数，然后我们还需要一个 $st$（可以使用 set 或者 multiset）记录每个连通块的大小，用于快速查找最大的那几个连通块的大小。

然后依次考虑 $d$ 个询问，假设第 $i$ 个限制是 $x$ 要和 $y$ 在一个连通块里，如果它们已经在一个连通块里了，我们只将 $cnt = cnt + 1$；否则的话先在 $st$ 里删除 $x$ 连通块大小和 $y$ 连通块大小，然后将 $x$ 连通块 和 $y$ 连通块 合并，最后再将新生成的连通块大小加入 $st$最后直接倒序遍历 $st$，求出最大的 $cnt + 1$ 个连通块的大小之和 $sum$，答案就是 $sum - 1$。

总的复杂度：$O(n^2)$。

查看代码 
#include <iostream>
#include <set>

const int N = 1e3 + 10;
int n, d;
int id[N], cnt[N];

// 并查集的查操作
int find(int p) {
    if (id[p] != p) id[p] = find(id[p]);
    return id[p];
}
// 并查集的并操作
void un(int p, int q) {
    int i = find(p), j = find(q);
    if (i == j) return;
    id[i] = j;
    cnt[j] += cnt[i];
}

int main() {
    scanf("%d%d", &n, &d);
    std::set<std::pair<int, int>> st;
    for (int i = 1; i <= n; ++ i) {
        id[i] = i, cnt[i] = 1;
        st.insert({1, i});
    }

    // Note: 这里使用 c 表示答案设计的连通块个数，而不是冗余边数
    int c = 1;
    for (int i = 0; i < d; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        int a = find(x), b = find(y);
        if (a == b) {
            ++c;
        } else {
            st.erase({cnt[a], a});
            st.erase({cnt[b], b});
            un(a, b);
            int idx = find(x);
            st.insert({cnt[idx], idx});
        }

        int ans = 0;
        // rbegin() 的意思是 reverse begin，即倒过来的开始
        // set 默认从小到大排序，使用此迭代器可以倒序遍历
        auto ptr = st.rbegin();
        for (int j = 0; j < c; ++j) {
            ans += ptr->first;
            ++ptr;
        }
        printf("%d\n", ans - 1);
    }
}

怎样想到这样写？

看了样例 2 后就会了……

$n$ 最大只有 $10^3$，所以可以暴力求和，边数很少（$d \le n - 1$），所以最多将所有点连成一棵树，不会出现加上冗余边后出现环的情况（也就是连通块数量小于 $cnt + 1$）。