题目
输入输出
数据范围
样例
输入样例：
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出样例：
4
0
题解
#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; }
