type
status
date
slug
summary
tags
category
icon
password
并查集
可以轻松计算出图中连通块的数量，以及判断两个点是否在同一个集合内，重点是需要进行路径压缩，否则可能会退化成链表查询，但并查集时间复杂度比较复杂，一般不做分析。
算法板子（重点就是写好这个find函数）：
例题（2024 美团暑期实习第一场笔试T5）
小美的朋友关系
小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。
输入描述
第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。
输出描述
对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。
数据范围
保证至少存在一次查询操作。
输入
输出
解释
第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。
第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问，显然 1 号和 4 号无法互相认识。
第四次事件，1 号和 2 号淡忘了。
第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。
思路与代码
并查集+逆向思维。
简单的连接问题使用并查集求解是非常方便的，但是这里涉及到删除边的操作。
我们不妨做如下假设：
- 找出所有可能要删除的边，然后假设所有边都删除了，构建一个最终的并查集。
- 逆向遍历所有的q次操作，如果是查询，使用并查集直接查出即可；如果是删除，则往并查集添加边。
- 作者:Kasyn
- 链接:https://kasyn.blog/article/disjoint-set
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章