1584_并查集

这是一道模板题。

维护一个 n 点的无向图，支持：

• 加入一条连接 u 和 v 的无向边

• 查询 u 和 v 的连通性

由于本题数据较大，因此输出的时候采用特殊的输出方式：用 0 或 1 代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353 的值。

第一行包含两个整数 n, m，表示点的个数和操作的数目。

接下来 m 行每行包括三个整数 op, u, v 。

• 如果 op=0，则表示加入一条连接 u 和 v 的无向边；

• 如果 op=1，则表示查询 u 和 v 的连通性。

n ≤ 4000000 , m ≤ 8000000

一行包括一个整数表示答案。

3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1

5

答案串为 101 。