← 返回题目列表

AtCoder · unionfind_a

B. 联合查找

中文机器翻译题面 查看原题

問題文

这个问题是讲座用问题。页面下方有解说。

N 考虑一个不一定简单的无向顶点图。 初始状态只有顶点,没有边,所有顶点都是孤立的。 下面 2 查询类型是 给予Q 次。

  • 串联查询:顶点 A 和顶点 添加一条连接 B 的边。
  • 决策查询:顶点 确定 A 和顶点 添加一条连接 B 是否是串联。如果是串联的话 Yes,否则 No 。

按顺序处理查询并输出判断查询的答案。 请注意,同一条边可能会添加多次,也可能会添加一条边本身。

连接意味着顶点 A 到顶点 这意味着可以通过沿着边缘到达 B 。 如果它们是相同的顶点,则定义要连接的 A 和 B 。 由于图是无向的,因此串联查询 当添加 A, B 之间的边时,A 它们的编号最大为 B 血 您还可以追踪到 B 它们的编号最大为 A 。


入力

输入将以以下格式从标准输入提供。

N Q
P_1 A_1 B_1
P_2 A_2 B_2
:
P_Q A_Q B_Q
  • 1 行包含一个表示顶点数的整数。 N (1≦N≦100,000) 和一个表示查询数量的整数 表示第 Q (1 ≦ Q ≦ 200,000) 用空格分隔。
  • 2 从线 Q 行数过多 关于第 i 第几行包含,i 个查询的类型的整数 P_i (0 ≦ P_i ≦ 1) 和一个表示要查询的顶点编号的整数 A_i, B_i (0 ≦ A_i, B_i ≦ N - 1) 用空格分隔。
    • P_i = 0 指示该查询是链接查询。
    • P_i = 1 表示该查询是判断查询。

出力

请输出每个判断查询。 在每个输出后添加换行符。


入力例1

8 9
0 1 2
0 3 2
1 1 3
1 1 4
0 2 4
1 4 1
0 4 2
0 0 0
1 0 0

出力例1

Yes
No
Yes
Yes

按以下步骤执行。

  • 1 在第二个查询中,顶点 1 和顶点 连接 2 。 对
  • 2 在第二个查询中,顶点 3 和顶点 连接 2 。 对
  • 3 在第二个查询中,顶点 1 和顶点 连接 3 进行连接判断。既然已经连接了, 输出Yes。 对
  • 4 在第二个查询中,顶点 1 和顶点 连接 4 进行连接判断。由于没有连接, 对No。 对
  • 5 在第二个查询中,顶点 2 和顶点 连接 4 。 对
  • 6 在第二个查询中,顶点 4 和顶点 连接 1 进行连接判断。它是连接的, 连接Yes。 对
  • 7 在第二个查询中,顶点 4 和顶点 连接 2 。这些已经连接,但可能会创建多个边。 连接
  • 8 在第二个查询中,顶点 0 和顶点 连接 0 。尽管这些是相同的顶点,但它们也可以形成自环。 对
  • 9 在第二个查询中,顶点 0 和顶点 连接 0 进行连接判断。由于相同的顶点总是可以被认为是相连的,Yes。 对