【题目链接】
ybt 1386：打击犯罪(black)文章来源：https://www.toymoban.com/news/detail-499226.html
【题目考点】
1. 并查集
【解题思路】
这是个无向图。每个犯罪团伙是一个顶点，犯罪团伙之间的联系是边，每个犯罪集团是一个连通分量。
以下描述中，连通分量就对应了并查集中集合的概念。
“犯罪团伙的危险程度”是连通分量中的顶点数。“最大的犯罪团伙的危险程度不超过n/2”，即为顶点数量最多的连通分量的顶点数量小于等于n/2。
按顺序打击团伙，相当于删掉当前图中的顶点，而后统计图中每个连通分量的顶点数量，这一过程过于繁琐。
题目中说只能按顺序打掉1到k的团伙，也就是按顺序删掉顶点1到k。此处可以进行逆向思维：删掉顶点1到k，相当于保留顶点k+1到n。
从一个空白的图开始，从顶点n到顶点1取每个顶点加入到图之中，针对每个顶点与图中已有顶点之间的边，进行合并操作。合并后只有该顶点所在的连通分量的数量发生了变化，因此只需要判断该连通分量中的顶点数是否大于n/2。文章来源地址https://www.toymoban.com/news/detail-499226.html
- 新增顶点n，判断n所在的连通分量顶点数量是否大于n/2。
- 新增顶点n-1，如果顶点n-1与顶点n之间有边，执行合并操作，判断n-1所在的连通分量顶点数量是否大于n/2。
- 新增顶点n-2，如果顶点n-2与顶点n-1到n之间有边，针对每条边执行合并操作，判断n-2所在的连通分量顶点数量是否大于n/2。
。。。 - 一般情况下，新增顶点k，如果顶点k与顶点k+1到n之间有边，针对每条边进行合并操作，判断k所在的连通分量顶点数量是否大于n/2。
如果k所在的连通分量顶点数量大于n/2，那么不应该把k作为保留在图中的顶点，应该删掉顶点1到k。也就是应该打掉团伙1到k，此时k的值就是该问题的结果。
【题解代码】
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int fa[N], ct[N], n;//ct[i]:以i为根结点的集合的顶点数
vector<int> edge[N];
void initFa(int n)
{
for(int i = 1; i <= n; ++i)
{
fa[i] = i;
ct[i] = 1;
}
}
int find(int x)
{
if(fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
void merge(int i, int j)
{
int x = find(i), y = find(j);
if(x != y)
{
ct[y] += ct[x];
fa[x] = y;
}
}
int main()
{
int m, t;
cin >> n;
for(int f = 1; f <= n; ++f)
{
cin >> m;
for(int i = 1; i <= m; ++i)
{
cin >> t;
edge[f].push_back(t);//edge[f]；保存f的邻接点，f和t有联系。
}
}
initFa(n);
for(int k = n; k >= 1; --k)
{
for(int v : edge[k])
if(v > k)//只取大于k的顶点
merge(k, v);//与k进行合并
if(ct[find(k)] > n/2)//如果合并后k所在的连通分量（集合）顶点数大于n/2
{
cout << k;//应该删除1~k
return 0;
}
}
return 0;
}
到了这里，关于信息学奥赛一本通 1386：打击犯罪(black)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
