原题链接: 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$)。