Educational Codeforces Round 56 D

题目大意：

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

给每个点赋值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 ;

}

巴特西

Educational Codeforces Round 56 D - Beautiful Graph

最新文章

热门文章