题意

这是一道模板题。

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

  • 加入一条连接 u 和 v 的无向边
  • 查询 u 和 v 的连通性

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

请务必使用快读。

输入格式

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

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

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

输出格式

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

样例

Input Output
3 6 1 1 0 0 0 1 1 0 1 1 1 2 0 2 1 1 2 1 5

答案串为 0101。

数据范围与提示

n≤4000000, m≤8000000

思路

这就是一道并查集的模板题。题中提到“请务必使用快读”，我暂时没发现有需要使用的地方，不过学习了快读的模板：

1
2
3
4
5
6
7
8
9
10
C++
inline int read() {
    int x = 0, f = 1; // f表示正负号
    char ch = getchar();
    while (ch < '0' || ch > '9')
        if (ch == '-') y = -1, ch = getchar();
    while (ch >= '0' && c <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * y;
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>

using namespace std;

const int N = 4e6 + 10, mod = 998244353;

int n, m, op, u, v;
int p[N], cnt;
long long res = 0, prod = 1;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- ) {
        scanf("%d%d%d", &op, &u, &v);
        if (op == 0) p[u] = v;
        else {
            if (find(u) == find(v)) {
                res *= 2;
                res ++ ;
                res %= mod;
            }
            else {
                res *= 2;
                res %= mod;
            }
        }
    }

    printf("%lld\n", res % mod);

    return 0;
}