#O1040. 并查集

并查集

题目描述

有 nn 个元素,初始时每个元素各自属于一个集合。执行 mm 次操作:

  • 1 a b:把 aa 与 bb 所在的两个集合合并;
  • 2 a b:询问 aa 与 bb 是否属于同一个集合。

题目类型

并查集

输入格式

第一行两个整数 n,mn, m。

接下来 mm 行,每行形如 1 a b 或 2 a b。

输出格式

对每个 2 a b 操作输出一行 YES 或 NO。

样例 #1

样例输入 #1

5 4
1 1 2
1 3 4
2 1 2
2 1 3

样例输出 #1

YES
NO

数据规模与约定

数据范围 说明
1≤n,m≤2×1051 \le n, m \le 2 \times 10^5 元素数与操作数
1≤a,b≤n1 \le a, b \le n 下标
  • 记得路径压缩,否则会超时。