Educational Codeforces Round 56—D

传送门

实际上我们可以发现这道题就是二分图染色

相邻的两点必然一个奇数一个偶数

而如果是奇数就有2种可能

对于每一个联通块我们都统计一下

考虑到如果其中某一个点的奇偶性确定了就可以确定整个联通块所有点的奇偶性

那我们就可以直接快速幂求出一个联通块的方案数

最后把所有联通块乘起来就是了

最好用$vector$方便很多

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
inline int read(){
    char ch=getchar();
    int res=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
const int N=500005;
int n,flag,m,cnt,tot,num,vis[N];
ll ans;
vector<int> e[N];
inline ll ksm(ll a,int p){ll ret=1;for(;p;p>>=1,a=a*a%mod)if(p&1)ret=ret*a%mod;return ret;}
inline void dfs(int u,int pos){
    if(!flag)return;num++;
    if(pos==1)vis[u]=2,tot++;
    else vis[u]=1;
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(vis[v]==vis[u]){
            flag=false;return;
        }
        if(vis[v])continue;
        dfs(v,(pos^1));
    }
}
int main(){
    int T=read();
    while(T--){
        n=read(),m=read(),ans=1,cnt=0,flag=1;
        for(int i=1;i<=n;i++)vis[i]=0,e[i].clear();
        for(int i=1;i<=m;++i){
            int u=read(),v=read();
            e[u].push_back(v),e[v].push_back(u);
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                num=tot=0;
                dfs(i,1);
                ans=ans*(ksm(2,tot)+ksm(2,num-tot))%mod;
            }
        }
        if(!flag)ans=0;
        cout<<ans<<'
';
    }
}