题目 30002

并查集

查看题解 ↗GitHub ↗如何评测
题号
30002
时间限制
10000 ms
内存限制
1024 MB
标签
数据结构并查集
来源
Library Checker (yosupo06) - unionfind

【题目描述】

有一个 NN 个顶点、00 条边的无向图。请依次处理以下 QQ 个查询:

  • $t_i$ = 0 $u_i$ $v_i$:添加一条边 (u,v)(u, v)。
  • $t_i$ = 1 $u_i$ $v_i$:若顶点 u,vu, v 连通,输出 11;否则输出 00。

【输入】

第一行包含两个整数 NN 和 QQ。

接下来 QQ 行,第 ii 行包含三个整数 ti ui vit_i\ u_i\ v_i,表示第 ii 个查询:

  • $t_i$ = 0 $u_i$ $v_i$:添加一条边 (u,v)(u, v)。
  • $t_i$ = 1 $u_i$ $v_i$:询问顶点 u,vu, v 是否连通。

【输出】

对每个 ti=1t_i = 1 的查询,输出一行:若顶点 u,vu, v 连通则输出 11,否则输出 00。

【输入样例】

文本
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

【输出样例】

文本
0
1
0
1

【数据范围】

  • 1≤N≤2000001 \leq N \leq 200000
  • 1≤Q≤2000001 \leq Q \leq 200000
  • 0≤ui,vi<N0 \leq u_i, v_i \lt N

【来源】

Library Checker(yosupo06) unionfind

数据下载

题目 30002 的公开数据

正在读取文件列表…

常用命令

题目 30002 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。