打击犯罪(black)（信息学奥赛一本通- P1386）

某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。

第一行一个正整数n。接下来的n行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第i行存在正整数k，表示i，k两个团伙可以直接联系。

一个正整数，为k的最小值。

【提示】

输出1（打击掉犯罪团伙）

1. 题目分析

问题核心：

我们需要按顺序（从1到k）打击掉前k个犯罪团伙成员。目标是求出最小的k，使得剩下的所有人中，最大的连通块（犯罪团伙）的大小不超过n/2。

难点：

并查集是一个非常擅长“合并”的数据结构，但它不擅长“删除”。如果按照题目正向思维，每删除一个人就要重新构建并查集，时间复杂度会爆炸。

2. 核心思路：

既然“删除”很难，那我们就把过程反过来！

1. 假设：我们先把1到n所有人全部“删除”（视为不存在）。

2. 复原：我们从第n个人开始，倒着往回一个一个“复活”（加入集合）。

   • 第 1 步：复活n。

   • 第 2 步：复活n-1。

   • ...

   • 第i步：复活i。

3. 判定：

   当我们“复活”了第i个人，并把他和已经存在的（编号大于i的）朋友合并后，如果发现此时最大的犯罪团伙人数超过了n/2。

   • 这就意味着：只要i存在，团伙就太大了。

   • 结论：为了不让团伙过大，我们必须把i也打击掉。所以i就是那个临界点，答案k=i。

3. 关键逻辑细节

• 只连“大于i”的人：在倒序遍历到i时，我们只能把i和编号大于i的朋友合并。因为编号小于i的人此时还处于“未复活”状态。

• 统计大小：每次合并后，我们需要扫描一遍当前所有“复活”的人，用一个d数组统计每个根节点下有多少人，从而找出最大值。

4. 完整代码

//为达到最好的效果，他们将按顺序打击掉 //编号1到k的犯罪团伙，请编程求出k的最小值 //k从小到大删，每删掉一个，代表输入的那一行的关系都不复存在 //所以我们可以倒着求，假设都删掉了，从最后可以开始复原，加入集合，求并查集 //当加到第i行时，犯罪团伙集团中最大的一个危险程度刚好大于n/2了 //就代表k的最小值就是i #include <iostream> #include <vector> using namespace std; vector<int> vec[1005];//存储输入的每一行的信息 int fa[1001];//记录每个犯罪团伙的集团老大 int d[1010];//记录每个犯罪集团的危险程度（每个老大集团有多少人） //查询 并进行路径压缩 int find(int x){ if(fa[x]==x) return x;//如果x的犯罪集团的老大就是x，就返回 //否则就递归求集团老大，并把路径上每个犯罪集团的老大变为最终老大 return fa[x]=find(fa[x]); } void uni(int x,int y){ int fax=find(x);//找到x的集团老大 int fay=find(y);//找到y的集团老大 //如果老大相同，就不需要任何操作 //否则就把x的集团老大变成y的集团老大的老大 if(fax!=fay){ fa[fay]=fax; } } int main(){ //关闭同步，加速 ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; //初始化每个犯罪团伙的老大是自己 for(int i=1;i<=n;i++) fa[i]=i; //把每一行输入信息都存进vector for(int i=1;i<=n;i++){ int m;//代表第i行有多少个数 cin>>m; for(int j=1;j<=m;j++){ int x; cin>>x; vec[i].push_back(x); } } //倒着遍历vector每一行 从第n行开始 //直到最大犯罪集团危险程度刚好超过n/2，就输出此时的i for(int i=n;i>=1;i--){ //把每一行的每一个大于i的元素和i放入同一个集团 //因为他们有直接联系 小于i的元素还没有复原 所以不能合并 for(int j=0;j<vec[i].size();j++){ //如果这一行的元素值大于i 就可以和i属于一个犯罪集团 if(vec[i][j]>i){ uni(i,vec[i][j]); } } int ma=1;//记录最大犯罪集团的危险程度 //接下来判断每个集团的危险程度 //d数组记录每个犯罪集团的危险程度（每个老大集团有多少人） memset(d,0,sizeof(d));//每轮要初始化d数组为0 //先做一次路径压缩，确保统计准确（也可以直接在find里做） for(int j=i;j<=n;j++) find(j); //因为现在比i小的都已经删掉了，还没复原，所以从i开始统计即可 for(int j=i;j<=n;j++){ d[find(j)]++;//找到j的老大，给这个老大的犯罪集团人数+1 ma=max(ma,d[find(j)]); } //当危险程度大于n/2时 说吗i必须删除 就输出当前i结束程序 if(ma>n/2){ cout<<i; return 0; } } return 0; }

5. 优化思考

目前的解法在统计人数时，每次都要遍历 i->n，这使得内部复杂度是O(N)，总复杂度接近 O(N^2)。对于N=1000的数据范围是完全没问题的。

如果N很大怎么办？

我们可以在并查集中维护一个 size[] 数组。

1. 初始化size[i]=1。

2. 在uni(x,y)合并时，直接size[fax]+=size[fay]，并实时维护一个全局最大值current_max。

3. 这样就不需要里面的memset和循环统计了，可以将复杂度降到接近O(N)。

优化后完整代码

//优化到O（n) //为达到最好的效果，他们将按顺序打击掉 //编号1到k的犯罪团伙，请编程求出k的最小值 //k从小到大删，每删掉一个，代表输入的那一行的关系都不复存在 //所以我们可以倒着求，假设都删掉了，从最后可以开始复原，加入集合，求并查集 //当加到第i行时，犯罪团伙集团中最大的一个危险程度刚好大于n/2了 //就代表k的最小值就是i #include <iostream> #include <vector> using namespace std; vector<int> vec[1005];//存储输入的每一行的信息 int fa[1001];//记录每个犯罪团伙的集团老大 int d[1010];//记录每个犯罪集团的危险程度（每个老大集团有多少人） int sz[1010];//记录每个犯罪集团有多少人 int ma;//记录最大犯罪集团的危险程度 //查询 并进行路径压缩 int find(int x){ if(fa[x]==x) return x;//如果x的犯罪集团的老大就是x，就返回 //否则就递归求集团老大，并把路径上每个犯罪集团的老大变为最终老大 return fa[x]=find(fa[x]); } void uni(int x,int y){ int fax=find(x);//找到x的集团老大 int fay=find(y);//找到y的集团老大 //如果老大相同，就不需要任何操作 //否则就把x的集团老大变成y的集团老大的老大 if(fax!=fay){ fa[fay]=fax; sz[fax]+=sz[fay];//fay的老大变成了fax，所以fay集团的人数要加到fax上 ma=max(ma,sz[fax]); } } int main(){ //关闭同步，加速 ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ fa[i]=i;//初始化每个犯罪团伙的老大是自己 sz[i]=1;//初始化每个犯罪团队都是一个犯罪集团，所以每个犯罪集团一个人 } //把每一行输入信息都存进vector for(int i=1;i<=n;i++){ int m;//代表第i行有多少个数 cin>>m; for(int j=1;j<=m;j++){ int x; cin>>x; vec[i].push_back(x); } } //倒着遍历vector每一行 从第n行开始 //直到最大犯罪集团危险程度刚好超过n/2，就输出此时的i for(int i=n;i>=1;i--){ //把每一行的每一个大于i的元素和i放入同一个集团 //因为他们有直接联系 小于i的元素还没有复原 所以不能合并 for(int j=0;j<vec[i].size();j++){ //如果这一行的元素值大于i 就可以和i属于一个犯罪集团 if(vec[i][j]>i){ uni(i,vec[i][j]); } } //当危险程度大于n/2时 说吗i必须删除 就输出当前i结束程序 if(ma>n/2){ cout<<i; return 0; } } return 0; }