第49场周赛第三题
二分图思路
黑白染色 , 记录黑色的数量cnt1,白色的数量cnt2
对于奇数有两种选择 , 而奇数既可以放黑色也可以放白色
因此对于一个连通块内的答案就是2^cnt1+2^cnt2
#include<bits/stdc++.h>
using namespace std;
const int N = 300010,M=N*2;
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
typedef long long LL;
const int Mod=998244353;
int cnt1,cnt2;
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
bool dfs(int u, int c)
{
color[u]=c;
if(c==1)cnt1++ ;
else cnt2++ ;
for (int i=h[u]; i!=-1; 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;
}
LL qmi(LL a,LL k,LL p){
LL res=1;
while(k){
if(k&1)res=res*a%p;
k=k>>1;
a=a*a%p;
}
return res;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++) h[i]=-1,color[i]=0;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
bool flag=true;
LL res=1;
for(int i=1;i<=n;i++){
if(!color[i]){
cnt1=0;
cnt2=0;
if(!dfs(i,1)){
flag=false;
break;
}else{
res=(LL)res*(qmi(2,cnt1,Mod)+qmi(2,cnt2,Mod))%Mod;
}
}
}
if(!flag)cout<<0<<endl;
else cout<<res<<endl;
}
return 0;
}