题解 CF1093D 【Beautiful Graph】

ouuan

2018-12-17 11:05:49

Solution

考虑每个联通块,对块内进行[黑白染色](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; } ```