4415. 点的赋值（二分图）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010, M = N << 1;
const int mod = 998244353;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int s1 = 0, s2 = 0;
bool dfs(int u, int c) {
    color[u] = c;
    if(c == 1) s1 ++;
    else s2 ++;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(color[j] && color[j] == c) return false;
        if(!color[j] && !dfs(j, 3 - c)) return false;
    }
    return true;
}
int pow2(int k) {
    int x = 1;
    while(k--) x = x * 2 % mod;
    return x;
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;  cin >> t;
    while (t--) {
        cin >> n >> m;
        memset(h, -1, (n + 1) * 4);
        memset(color, 0, (n + 1) * 4);
        idx = 0;
        int res = 1;
        while (m -- ) {
            int a, b; cin >> a >> b;
            add(a, b), add(b, a);
        }
        for (int i = 1; i <= n; i++) {
            if(!color[i]) { // 对每一个连通块处理
                s1 = s2 = 0;
                if(!dfs(i, 1)) {
                    res = 0;
                    break;
                }
                res = res * (long long)(pow2(s1) + pow2(s2)) % mod;
            }
        }
        cout << res << endl;
    }
    return 0;
}