#H. 并查集

    Type: Default 1000ms 256MiB

并查集

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道模板题。

维护一个 nn 点的无向图,支持:

  • 加入一条连接 uuvv 的无向边
  • 查询 uuvv 的连通性

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

请务必使用快读。

输入格式

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

接下来 mm 行每行包括三个整数 op,u,v\text{op},u,v

  • 如果 op=0\text{op} = 0,则表示加入一条连接 uuvv 的无向边;
  • 如果 op=1\text{op} = 1,则表示查询 uuvv 的连通性。

输出格式

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

样例

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

答案串为 01010101

数据范围与提示

n4000000,m8000000n\le 4000000,m\le 8000000

By zyz

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45