题目实战（2）：数据结构——并查集

零、进食后入

并查集一定要初始化，即 fa i = i \text{fa}_i=i fai​=i，表示i的爹是它自己……

一、题目

1、团伙

给定 n n n 个人， m m m 个关系，每个关系为 x x x 和 y y y 是朋友/敌人。求最多的团体数。（两个人在一个团体内当且仅当这两个人是朋友）

首先， “敌人的敌人就是朋友”可以这么理解：如果一个人有两个或更多敌人，这些敌人就应该被合并。

我们如果发现有两个人是朋友，那就无条件合并。

但如果设 x x x 和 y y y 是敌人，那么 x x x 和 y y y 的敌人就是朋友。

所以，我们给每个人开两个域：

• x x x：表示 x x x 本身
• x + n x+n x+n：表示 x x x 的敌人集合

然后，我们只要做简单的输入处理即可：

• x x x 和 y y y 是朋友
  • union ( x , y ) ; \text{union}(x,y); union(x,y);
• x x x 和 y y y 是敌人
  • union ( x + n , y ) ; \text{union}(x+n,y); union(x+n,y);
  • union ( x , y + n ) ; \text{union}(x,y+n); union(x,y+n);

END。

如果你AC了本题，建议做做食物链这道题。

2、程序自动分析

发现NOI喜欢出并查集。

给定一些判定条件（ x i = x j x_i=x_j xi​=xj​ or x i ≠ x j x_i \neq x_j xi​=xj​），让你判断是否有一组解，使得全部满足。

应为只有两种条件，所以我们先处理等于的操作。题目中只有相等/不相等，所以我们把所有相等的放一个集合里。然后我们处理不等，其实只要判断一下是否在一个集合里即可。

然后我们再看一下这个令人唏嘘感叹的 fa \text{fa} fa 数组： n ≤ 10 9 n \le 10^9 n≤109，你可以去开一个试试看。如果你AC了，那你就是

然后就会获得一个RE……

怎么办呢？说一个大概看本文的人都不知道的数据处理方式：离散化！

不知道的可以看这个：出门左转

一个比较能让人懵的算法啊，总的来说就是这个：

• 当你在处理数字很大（ n ≤ 10 9 n \le 10^9 n≤109），但数字很小（ 1 ≤ t ≤ 10 1 \le t \le 10 1≤t≤10）的时候，我们可以把约束的所有 x x x y y y
• 去重；
• 排序；
• 给每个唯一的数值分配一个连续的小下标；
• 然后再用并查集先处理相等的变量，再遍历所有的不等约束。

然后你就开开心心的AC了这道题。

3、集合

给定区间 [ a , b ] [a, b] [a,b]（ 1 ≤ a ≤ b ≤ 10 5 1 \le a \le b \le 10^5 1≤a≤b≤105）和 m m m 个查询，每个查询问两个数 x 、 y x、y x、y 是否在同一个集合里。

集合规则：如果两个数有公共的质因子，它们就属于同一个集合（关系有传递性）。

“有公共质因子”这件事，可以理解成：用这个质因子当“桥”，把所有包含它的数合并到一起。

比如：

• 6 6 6 的质因子是 2 、 3 2、3 2、3
• 8 8 8 的质因子是 2 2 2
• 9 9 9 的质因子是 3 3 3

用质因子 2 2 2 合并 6 6 6 和 8 8 8，用质因子 3 3 3 合并 6 6 6 和 9 9 9，最后 6 6 6、 8 8 8、 9 9 9 就都在一个集合里了。

那我们只要用质筛求质数，符合条件点的连边（与自己的质因数），最后灌水即可。