题解 CF1093D 【Beautiful Graph】
ouuan
2018-12-17 11:05:49
考虑每个联通块,对块内进行[黑白染色](https://www.cnblogs.com/zhangjiuding/p/7710811.html)。
若无解(不是二分图),直接输出 $0$,不用继续判断其它联通块;
若有解,统计黑点个数 $b$,白点个数 $w$。我们可以把黑点设成奇数,白点设成偶数,此时方案数为 $2^b$,反之则为 $2^w$。(为奇数时 $1,3$ 任选,为偶数时只能选 $2$)
将每个联通块的方案数相乘即是答案。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=300010;
const int M=998244353;
void add(int u,int v);
void dfs(int u);
int head[N],nxt[N<<1],to[N<<1],cnt;
int t,n,m,c[N],tot[2],ans,two[N];
bool flag;
int main()
{
int i,u,v;
two[0]=1; //预处理2的次幂
for (i=1;i<N;++i)
{
two[i]=two[i-1]*2%M;
}
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
memset(head,0,sizeof(int)*(n+1)); //如果memset整个数组可能被卡到O(maxn*t)
memset(c,-1,sizeof(int)*(n+1));
cnt=0;
ans=1;
flag=false;
for (i=0;i<m;++i)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for (i=1;i<=n&&!flag;++i)
{
if (c[i]==-1)
{
tot[0]=tot[1]=c[i]=0;
dfs(i);
ans=1ll*ans*(two[tot[0]]+two[tot[1]])%M;
}
}
if (flag)
{
puts("0");
}
else
{
printf("%d\n",ans);
}
}
return 0;
}
void dfs(int u)
{
++tot[c[u]];
int i,v;
for (i=head[u];i;i=nxt[i])
{
v=to[i];
if (c[v]==-1)
{
c[v]=c[u]^1;
dfs(v);
if (flag)
{
return;
}
}
else if (c[v]==c[u])
{
flag=true;
return;
}
}
}
void add(int u,int v)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
```