【题目描述】
有一个 N 个顶点、0 条边的无向图。请依次处理以下 Q 个查询:
$t_i$ = 0 $u_i$ $v_i$:添加一条边 (u,v)。
$t_i$ = 1 $u_i$ $v_i$:若顶点 u,v 连通,输出 1;否则输出 0。
【输入】
第一行包含两个整数 N 和 Q。
接下来 Q 行,第 i 行包含三个整数 ti ui vi,表示第 i 个查询:
$t_i$ = 0 $u_i$ $v_i$:添加一条边 (u,v)。
$t_i$ = 1 $u_i$ $v_i$:询问顶点 u,v 是否连通。
【输出】
对每个 ti=1 的查询,输出一行:若顶点 u,v 连通则输出 1,否则输出 0。
【输入样例】
文本
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
【输出样例】
【数据范围】
- 1≤N≤200000
- 1≤Q≤200000
- 0≤ui,vi<N
【来源】
Library Checker(yosupo06) unionfind