美团 · 并查集 · 算法编程题
美团 并查集 m ≤ 1e5 时限 1 秒 / 256 MB

题目描述

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 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 ，含义如题目描述所述。
1≤ n ≤ 10^9
1≤ m,q ≤ 10^5
1≤ u,v ≤ n
1≤ op ≤ 2
保证至少存在一次查询操作。
输出描述
对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。

样例共 1 组

样例 1 · 第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。 第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。 第三次事件是询问，显然 1 号和 4 号无法互相认识。 第四次事件，1 号和 2 号淡忘了。 第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。
输入
5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3
输出
Yes
No
No

算法解析依据充分

考点：并查集

数据规模 m ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：m ≤ 1e5，q ≤ 1e5
  • 元素值域：n ≤ 1e9，op ≤ 2（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：并查集

本题切入点

只有删边没有加边，正序难维护；把操作序列倒过来处理就变成「只加边」，用并查集回答连通性询问。

用「代表元」高效维护集合合并与连通性查询，均摊近 O(1)。

思路框架（并查集 通法 · 非本题专属）

  1. 初始化 parent[i] = i。
  2. find(x) 找根节点，路径压缩把链压平。
  3. union(x,y) 把两个根合并（按秩/大小合并更优）。
  4. 最终统计有几个不同的根，即有多少个连通块。

实现要点：路径压缩 + 按大小合并，复杂度近似 O(α(n))。

复杂度：时间 O(n α(n)) ｜ 空间 O(n)

该范式的通法易错点

  • 只做路径压缩没做按秩合并，极坏情况下仍会退化。
  • 统计连通块时忘了再压缩一次根。

对照本题

  • 数据规模 m ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 5 3 5 / 1 2 / 2 3 / 4 5 / 1 1 5 / 2 1 3 / 2 1 4 / 1 1 2 / 2 1 3 → 输出 Yes / No / No

第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。

第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。

第三次事件是询问，显然 1 号和 4 号无法互相认识。

第四次事件，1 号和 2 号淡忘了。

第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2024年春招-美团-算法策略-第一批笔试；2024年春招-美团-技术岗-第一批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解