分析
这其实是一道数学题,对于一个连通块,内部必须是二分图,不然无法整个连通块进行赋值
假设将某个连通块分为$A(x$个点)、$B(y$个点)两部分,
① 如果$A$分$1/3$,$B$分$2$,那么有一共有$2^x$中方案
② 如果$B$分$1/3$,$A$分$2$,那么有一共有$2^y$中方案
所以对于一个连通块,一共有$2^x+2^y$中方案
因为所有连通块是组合的,所以总方案数为所有连通块方案累乘
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10, M = N * 2, mod = 998244353;
typedef long long LL;
int col[N], s1, s2;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int pow2(int k)
{
int res = 1;
while (k --) res = res * 2 % mod;
return res;
}
bool dfs(int u, int c)
{
col[u] = c;
if (c == 1) s1 ++;
else s2 ++;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!col[j])
{
if (!dfs(j, 3 - c)) return false;
}
else if (col[j] == c) return false;
}
return true;
}
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
int n, m;
scanf("%d%d", &n, &m);
memset(h, -1, (n + 1) * 4);
memset(col, 0, (n + 1) * 4);
while (m --)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
int res = 1;
for (int i = 1; i <= n; i ++)
if (!col[i])
{
s1 = s2 = 0;
if (dfs(i, 1)) res = (LL) res * (pow2(s1) + pow2(s2)) % mod;
else
{
res = 0;
break;
}
}
printf("%d\n", res);
}
return 0;
}