打击犯罪(black)

线上OJ：

一本通：1386：打击犯罪(black)

核心思想：

1、如果按照题意，从1~k的顺序进行删除（枚举），则每次枚举完都要重置并查集，比较麻烦。

2、考虑逆向思维， 不从1 ~ k 顺序删除，而是从 n ~ k 逆序往图中添加。

a. 如果添加到 k 时，最大集合的元素数量不超过 n/2 ，则说明k还可以继续减小

b. 如果添加到 k 时，最大集合的元素数量开始超过 n/2，则这个 k 点不能加入，也就是说：这个k点必须删除

备注：这个点k就是题目要求的k的最小值。因为把k删除后，最大集合的元素数量不超过 n/2；如果把比k大的元素删除，更加不会超过n/2。

3、初始化每个节点时，除了初始化p[i]=i，还要初始化cnt[i] = 1，表示 i 所在集合的元素的数量仅为自己。

4、由于是逆序把 k 添加进图（图中只有比k大的点），所以在分析k 的边时，只考虑已经在图中的点（即e[k][j] > k的点）

5、如果点k和点e[k][j] 尚不在一个集合中，则合并根节点，并更新根节点所在集合的元素数量（此处不需要更新每个点的cnt，只需更新根节点的cnt，因为后续的累加也只拿根节点来累加）

题解代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, p[N], cnt[N]; // p[i]表示 i 的根节点；cnt[i] 表示 i 所在集合的元素的数量
int e[N][N]; // e[i][0] 存储 i 有几条边；e[i][1] 存储 i 的第 1 条边连接的点... e[i][j] 存储 i 的第 j 条边连接的点

int find(int x)  // 找根节点
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        p[i] = i;  // 初始化每个元素的根节点为自己（即每个元素都是独立的）
        cnt[i] = 1;// 初始化时，每个元素所在的集合都只有自己，所以 cnt 均为 1
    }

    // 读入数据，建立边
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &e[i][0]); // 先存入i号节点边的数量
        for(int j = 1; j <= e[i][0]; j++)
            scanf("%d", &e[i][j]); // 再存入 i 的第 j 条边连接的点
    }

    // 核心代码：逆向处理，每次把 k 加入图中，并看新加入点导致的集合数量是否超过n/2
    for(int k = n; k >= 1; k --)  
    {
        for(int j = 1; j <= e[k][0]; j++)  // 分析与k相连的每一个点
        {
            if(e[k][j] > k)  // 由于是逆向把点加入图中。所以只有编号 >k 的点当前才在图中，才需要合并
            {
                int x = find(k), y = find(e[k][j]);
                if(x != y) // 如果点k和点e[k][j] 尚不在一个集合中
                {
                    p[y] = x;  // 则合并根节点
                    cnt[x] += cnt[y]; // 更新根节点所在集合的元素数量（此处不需要更新每个点的cnt,只需更新根节点的cnt，因为后续的累加也只拿根节点来累加）
                    if(cnt[x] * 2 > n)
                    {
                        printf("%d\n", k);
                        return 0;
                    }
                }
            }
        }
    }

    return 0;
}