Educational Codeforces Round 56 D - Beautiful Graph

​题目大意：

在给定的一个图中（可能不连通）

给每个点赋值1、2、3 使得一条边上的两个端点点权相加为奇数

求方案数

一条满足条件的路径上的点权必为一奇一偶交替

偶数只有2 奇数有1、3

若位于1、3、5、.... 的点有x1个 位于2、4、6、... 的点有x0个

那么一条路径的方案数为 2^x1+2^x0 （x1的点作为奇数点的方案+x0的点作为奇数点的方案）

当图不连通 存在多个子图 那么每个子图的方案数相乘 就是总的方案数

当图中存在环时 若环上的点数为偶数则同样满足上式 但为奇数则整条路径不可能有解

#include <bits/stdc++.h>

#define LL long long

#define mod 998244353

using namespace std;

int n,m;

const int N=3e5+;

vector <int> e[N];

bool vis[N], NO;

int col[N], m0, m1;

LL p[N];

void init() {

    p[]=1LL;

    for(int i=;i<N;i++)

        p[i]=p[i-]*2LL%mod;

}

void dfs(int u,int c) {

    if(NO) return;

    col[u]=c;

    if(col[u]) m1++;

    else m0++;

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

        int v=e[u][i];

        if(col[v]==-) dfs(v,c^);

        else if(col[v]==col[u]) {

            NO=; return; // 环上的点数为奇数个

        }

    }

}

int main()

{

    init();

    int t; scanf("%d",&t);

    while(t--) {

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)

            e[i].clear(), col[i]=-;

        for(int i=;i<m;i++) {

            int u,v; scanf("%d%d",&u,&v);

            e[u].push_back(v), e[v].push_back(u);

        }

        LL ans=1LL; NO=;

        for(int i=;i<=n;i++)

            if(col[i]==-) {

                m0=m1=; dfs(i,);

                if(NO) break;

                ans=(p[m0]+p[m1])%mod*ans%mod;

            }

        if(NO) printf("0\n");

        else printf("%I64d\n",ans);

    }

    return ;

}