信息
- ID
- 5540
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
#include <iostream>
using namespace std;
const int P = 998244353;
int fa[4000010];
int find(int x)
{
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y)
{
fa[find(x)] = find(y);
}
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
fa[i] = i;
int k, x, y, ans = 0;
while (m--)
{
cin >> k >> x >> y;
if (k == 0)
merge(x, y);
else if (find(x) == find(y))
ans = (ans << 1) + 1, ans %= P;
else
ans = ans << 1, ans %= P;
}
cout << ans << '\n';
return 0;
}