这个题深搜容易解决, 结果用了广搜, 动手之前还是要想清楚, 然后自己的代码写错的情况下, 没有重写, 而是在原有的基础上, 进行修改, 结果有个判定的初始化条件放错位置, 浪费了一个小时...
就是给一个无向图, 任务时给点附上 1,2, 或者 3, 使得每条边相连的两个顶点数字之和位基数, 求一共有多少种方案.
本来准备放自己的代码, 算了, 还是官方题解比较简洁, 有那个 for 写的很短, 而且我写的有好几个函数, 检查起来跳来跳去的, 以后短的代码还是尽量写在主函数吧
- #include <bits/stdc++.h>
- using namespace std;
- const int N = int(3e5) + 999;
- const int MOD = 998244353;
- int n, m;
- vector <int> g[N];
- int p2[N];
- int cnt[2];
- int col[N];
- bool bad;
- void dfs(int v, int c){
- col[v] = c;
- ++cnt[c];
- for(auto to : g[v]){
- if(col[to] == -1) dfs(to, 1 - c);
- if((col[v] ==col[to]) )
- bad = true;
- }
- }
- int main() {
- p2[0] = 1;
- for(int i = 1; i < N; ++i)
- p2[i] = (2 * p2[i - 1]) % MOD;
- int tc;
- scanf("%d", &tc);
- while(tc--){
- scanf("%d%d", &n, &m);
- for(int i = 0; i < n; ++i)
- g[i].clear();
- for(int i = 0; i < m; ++i){
- int u, v;
- scanf("%d %d", &u, &v);
- --u, --v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- int res = 1;
- for(int i = 0; i < n; ++i) col[i] = -1;
- for(int i = 0; i < n; ++i){
- if(col[i] != -1) continue;
- bad = false;
- cnt[0] = cnt[1] = 0;
- dfs(i, 0);
- if(bad){
- puts("0");
- break;
- }
- int cur = (p2[cnt[0]] + p2[cnt[1]]) % MOD;
- res = (res * 1LL * cur) % MOD;
- }
- if(!bad) printf("%d\n", res);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3438581.html