【Codeforces】1609D 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;
}