正文

[并查集]团伙

skylee的OI博客  skylee的OI博客  2022-09-03  293

关键词：

题号：ZHOJ1258

思路：并查集。

给每个人建立一个“正集”（朋友）、一个“反集”（敌人），反集要么为空、要么指向一个正集，维护这两类集合，最后统计“正集”的个数。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int N=1000;
 4 int ans;
 5 class UnionFindSet {
 6     private:
 7         int anc[N],anti[N];
 8     public:
 9         UnionFindSet(int n) {
10             for(int i=0;i<=n;i++) {
11                 anc[i]=i;
12                 anti[i]=0;
13             }
14         }
15         int Find(int x) {
16             return (x==anc[x])?x:(anc[x]=Find(anc[x]));
17         }
18         void Union(int op,int x,int y) {
19             if(op==1) {
20                 if(Find(y)==Find(x)) return;
21                 anc[Find(y)]=Find(x);
22             }
23             if(op==2) {
24                 if(anti[x]) Union(1,anti[x],y);
25                 if(anti[y]) Union(1,anti[y],x);
26                 if(!anti[x]) anti[x]=Find(y);
27                 if(!anti[y]) anti[y]=Find(x);
28             }
29         }
30         int Count(int n) {
31             bool vis[n+1];
32             memset(vis,0,sizeof vis);
33             for(int i=1;i<=n;i++) vis[Find(i)]=true;
34             int ans=0;
35             for(int i=1;i<=n;i++) if(vis[i]) ans++;
36             return ans;
37         }
38 };
39 int main() {
40     int n,m;
41     scanf("%d%d",&n,&m);
42     UnionFindSet s(n);
43     while(m--) {
44         int op,x,y;
45         scanf("%d%d%d",&op,&x,&y);
46         s.Union(op,x,y);
47     }
48     printf("%d
",s.Count(n));
49     return 0;
50 }

团伙（并查集经典）

题目大体的说：1.我朋友的朋友是我的朋友； 2.我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可... 查看详情

并查集bzoj1370-[baltic2003]gang团伙

【题目大意】在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋... 查看详情

续并查集学习笔记——gang团伙题解

一言不合先贴题目Description在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即... 查看详情

动规(18)-并查集基础题——团伙

在某城市里住着N个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、我朋友的朋友是我的朋友； 2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息&#... 查看详情

bzoj1370[baltic2003]gang团伙：并查集虚点

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1370题意：　　在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：　　　　（1）我朋友的朋友是我的朋友。　　　　（2）我敌人的敌人是我的朋友。　　所... 查看详情

p1892[boi2003]团伙并查集(代码片段)

题目描述1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅... 查看详情

动规(18)-并查集基础题——团伙(代码片段)

动规(20)-并查集基础题——打击犯罪(代码片段)

【问题描述】　某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情

动规(20)-并查集基础题——打击犯罪(代码片段)

bzoj1370:[baltic2003]gang团伙（luogu1892）（种类并查集）(代码片段)

...吧　　https://www.luogu.org/problemnew/show/P1892题解：　　种类并查集。。　　因为有敌人的敌人是朋友这个条件，所以需要一个中转点。。　　因此，将每个点拆成两个点，一个是朋友点，另一个是敌人点。当读到A与B是朋友时，就将... 查看详情

并查集的一般操作③

RT 题目描述 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同... 查看详情

并查集

并查集是一个非常非常简单，好背，但不好理解的题目，但只要理解了，闭着眼都能打出来，当然我也因为这个困扰了好长时间，接下来我给大家说说并查集支持的许多操作。1：找爸爸（find）不要在意名字，这不是帮你理解吗... 查看详情

[洛谷p1892]团伙

...人就不在，现在给出一关系，问最多有多少团伙。题解：并查集，建反集，如果是朋友，就把他们的并查集合并；如果是敌人，就把他们分别和对方的反集合并，统计最后有几个联通块C++Code：#include<cstdio>usingnamespacestd;constin... 查看详情

[qbzt寒假]并查集(代码片段)

并查集：(Kruscal)，(Tarjan)求(LCA)分类并查集：食物链，团伙（敌人的敌人是我的朋友）带权并查集：(SDOI2016)齿轮（可用intfather(intx)returnfa[x]==x?x:fa[x]=father(f[x]);Luogu3101滑雪等级[]建边：任意相邻两格子之间建边，权值为海拔差将边... 查看详情

❤️数据结构入门❤️（2-5）-并查集

文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情

并查集

并查集1.并查集是什么并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。查询元素a和元素b是否属于同一组。合并元素a和元... 查看详情