Codeforces 1093D. Beautiful Graph【二分图染色】+【组合数】

题目大意：

给你一个无向图(该无向图无自环，且无重边)，现在要你给这个无向图的点加权，所加权值可以是1,2,3。给这些点加权之后，要使得任意边的两个端点权值之和为奇数，问总共有多少种可能？结果mod 998244353。

解题分析：

整张图的所有顶点赋权之后，一定分为奇、偶两部分点集，并且，要想使的该图满足条件，任意边的两个端点的奇偶性应该是不同的，所以我们可以用DFS对图进行二分图染色，将图分为两个部分，需要注意的是，该图未必连通。然后就是DFS的过程中，如果下一个点已经染过色，且颜色与当前点颜色相同，说明该图不符合条件。将当前连通分量分成两部分之后，也有两种情况，一是：第一部分为奇数，因为奇数有1、3两种选择，所以情况有 2^cnt1 种；二是：第二部分是奇数，则情况有 2^cnt2 种。然后再将所有连通分量的情况相乘，就是最终得到的所有情况。

#include <bits/stdc++.h>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define pb push_back

typedef long long ll;

const ll MOD = ;

const int N = 3e5+;

int n,m,cnt1,cnt2;

int col[N];

ll ans,fact[N];

bool fp;

vector<int>G[N];

void dfs(int u){

  if(col[u]==)cnt1++;

  else cnt2++;

  for(int i=;i<G[u].size();i++){

    int v=G[u][i];

    if(col[u]==col[v]){ fp=false;return; }

    if(col[v])continue;

    col[v]=col[u]^;       //将二分图染成编号为2、3的色块

    dfs(v);

  }

}

int main(){

  ios::sync_with_stdio(false);cin.tie();cout.tie();

  fact[]=;REP(i,,N-)fact[i]=fact[i-]*%MOD;         //计算2的阶乘

  int T;cin>>T;while(T--){

    cin>>n>>m;

    REP(i,,n)G[i].clear(),col[i]=;

    REP(i,,m){

      int u,v;cin>>u>>v;

      G[u].pb(v);G[v].pb(u);

    }

    fp=true;ans=;

    REP(i,,n) if(!col[i]){

      cnt1=cnt2=;

      col[i]=;dfs(i);

      if(!fp){ ans=;break; }

      ans*=1LL*(fact[cnt1]+fact[cnt2]);  //如果2的部分填奇数，因为每个奇数点都有两种选择，所以有fact[cnt1]种情况，如果3的部分填奇数，则有fact[cnt2]种情况

      ans%=MOD;

    }

    printf("%lld\n",ans%MOD);

  }

}