MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 CF1093D 【Beautiful Graph】

posted on 2018-12-17 17:50:37 | under 题解 |

当时并不会做,看题解后恍然大悟。

因为只能标$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$的点发生变化,所以要将方案数相加),再将每个连通块的方案数相乘就好了(乘法原理)

#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;
}