提前感谢大佬们帮看代码!!!感谢!!
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10, M = 6e5 + 10;
const int MOD = 998244353;
int h[N], e[N], ne[N], idx;
int st[N];
int n, m;
int k1 = 0, k2 = 0;
void init() {
idx = 0;
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u) {
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(!st[j]) {
st[j] = 3 - st[u];
if(st[j] % 2 == 1) k1++;
else k2++;
if(!dfs(j)) return false;
} else {
if(st[j] == st[u]) return false;
}
}
return true;
}
int qmi(int u, int k) {
LL sum = 1, t = u;
while(k) {
if(k & 1) sum = sum * t % MOD;
k >>= 1;
t = t * t % MOD;
}
return sum;
}
int main()
{
int T, a, b;
scanf("%d", &T);
while(T--) {
init();
scanf("%d%d", &n, &m);
if(m == 0) {
LL ans = qmi(3, n);
printf("%lld\n", ans);
continue;
}
while(m--) {
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
LL s = 1;
for(int i = 1; i <= n; i++) {
if(!st[i]) {
st[i] = 1;
k1 = 1, k2 = 0;
if(!dfs(i)) {
s = 0;
break;
}
int cur = (qmi(2, k1) + qmi(2, k2)) % MOD;
s = (s * cur) % MOD;
}
}
printf("%lld\n", s);
}
return 0;
}