题目链接: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;
}