ouuan 的博客

ouuan 的博客

题解 CF1093D 【Beautiful Graph】

posted on 2018-12-17 11:05:49 | under 题解 |

考虑每个联通块,对块内进行黑白染色

若无解(不是二分图),直接输出 $0$,不用继续判断其它联通块;

若有解,统计黑点个数 $b$,白点个数 $w$。我们可以把黑点设成奇数,白点设成偶数,此时方案数为 $2^b$,反之则为 $2^w$。(为奇数时 $1,3$ 任选,为偶数时只能选 $2$)

将每个联通块的方案数相乘即是答案。

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