SSL2342 打击犯罪【并查集】

这道题思路很巧妙。
我们先假设所有的犯罪团伙都被打击掉了，
那么此时我们重新从 $n->1$ 复活犯罪团伙（也就是将它们并在一起）。
当我们发现无论怎么并，犯罪团伙的危险程度都$>n/2$时，就停止并操作。
此时我们直接输出 $i$ 即可。( $i$ 为当前被打击掉的团伙)

代码：

#include
#include
#include
using namespace std;
int n,s[1010],rank[10010],fa[10010],a[1010][1010];
int find(int x)
{if(fa[x]==x)return fa[x];return fa[x]=find(fa[x]);
}
int main()
{cin>>n;for(int i=1; i<=n; i++){cin>>s[i];for(int j=1; j<=s[i]; j++)cin>>a[i][j];}for(int j=1; j<=n; j++){rank[j]=1;fa[j]=j;}for(int i=n; i>=1; i--)   //n到1复活{for(int k=1; k<=s[i]; k++){if(a[i][k]<=i)   //不能先复活前面的犯罪集团continue;int k1=find(i);int k2=find(a[i][k]);if(k1!=k2)  //不是同一个犯罪团伙{fa[k1]=k2;   //复活（并）rank[k2]+=rank[k1];  //统计危险程度if(rank[k2]>n/2)  //如果危险程度已经>n/2{cout<<i;   //直接输出return 0;}} }}return 0;
}

编写不易，请多指点、点赞 ！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！