LibreOJ 109 并查集

题目链接:LibreOJ 109 并查集

题目大意:
LibreOJ 109 并查集

题解:
并查集模板,结果用二进制表示,注意要快读。

#include <cstdio>
#include <iostream>
using namespace std;

int fa[4000010], ans;

inline int read() {
    char ch = getchar();
    int ans = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ans = (ans << 3) + (ans << 1) + (ch ^ 48);
        ch = getchar();
    }
    return ans * f;
}

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void uni(int x, int y) {
    int fax = find(x);
    int fay = find(y);
    if (fax != fay) {
        fa[fax] = fay;
    }
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        int act = read();
        if (act == 0) {
            int x = read(), y = read();
            uni(x, y);
        } else {
            int x = read(), y = read();
            ans = ((ans << 1) + (find(x) == find(y))) % 998244353;
        }
    }
    printf("%d", ans);
    return 0;
}
上一篇:python刷题--N数之和问题(双指针+剪枝)


下一篇:scanf 和 getchar