题解 CF1093D 【Beautiful Graph】
MorsLin
2018-12-17 17:50:37
当时并不会做，看题解后恍然大悟。
因为只能标$1,2,3$三个数，且相连的两个点加起来必须为奇数，那么只有这两种情况$1-2\;,\;3-2$。我们可以发现，当这个图中存在一个长度为奇数的环的时候是肯定无解的，换句话说，**当且仅当这张图是一张二分图的时候有解**。
这就启发我们了，当有解的时候，我们还可以发现，当一个点 点权为$2$且每有一条出边的时候，当前的方案数是要$\times 2$的，因为$2$可以连$1$或$3$；反之，方案数不变，因为$1,3$只能去连$2$。
到这里，思路就很清晰了，对于每一个连通块，我们跑一遍二分图染色，记录下两部分的点的个数，分别计为$s_1,s_2$，那么这个连通块的方案数为$2^{s_1}+2^{s_2}$(因为起始点既可以标$1$或$3$，也可以标$2$，这两种方案会导致标$2$的点发生变化，所以要将方案数相加)，再将每个连通块的方案数相乘就好了(乘法原理)
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 998244353
#define LL long long
using namespace std;
struct zzz{
int t,nex;
}e[300010<<1]; int head[300010],tot;
inline void add(int x,int y){
e[++tot].t=y;
e[tot].nex=head[x];
head[x]=tot;
}
int vis[300010];
LL sum[5],ans;
bool dfs(int x){
for(int i=head[x];i;i=e[i].nex){
if(vis[e[i].t]==-1){
vis[e[i].t]=(vis[x]^1);
if(!dfs(e[i].t)) return 0;;
}
else{
if(vis[e[i].t]==vis[x])
return 0;
}
}
sum[vis[x]]++;
return 1;
}
LL qpow(LL b,LL p){
LL ans=1;
while(p){
if(p&1) ans=(ans*b)%mod;
b=(b*b)%mod;
p>>=1;
}
return ans;
}
inline int read(){
int k=0,f=1; char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
k=k*10+c-48,c=getchar();
return k*f;
}
int main(){
int t=read();
qwq:
while(t--){
bool flag=0;
ans=1; tot=0;
int n=read(),m=read();
for(int i=0;i<=n;i++) vis[i]=-1,head[i]=0;
for(int i=1;i<=m;i++){
int x=read(),y=read();
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++){
sum[0]=sum[1]=0;
if(vis[i]==-1){
vis[i]=1;
if(!dfs(i)){
flag=1; printf("0\n"); goto qwq;
}
else
ans=(ans*(((qpow(2,sum[0]))%mod+qpow(2,sum[1]))%mod))%mod;
}
}
if(!flag) printf("%lld\n",ans);
}
return 0;
}
```