零、进食后入
并查集一定要初始化，即
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
xy
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 就都在一个集合里了。
那我们只要用质筛求质数，符合条件点的连边（与自己的质因数），最后灌水即可。
