Codeforces 1093D Beautiful Graph_codeforces - 1093d

题目链接：http://codeforces.com/contest/1093/problem/D
第一次做这种题目，染色+组合数学。。
假设这个图里有奇数环，那么肯定是不行的，因为无论怎么样都是偶数。
如果没有奇数环。那么对于任意一个连通分支，一条边所连得两个点，肯定有一个是2，另外的是1或者3。如果将每条边连接的两个点染成黑点和白点。个数分别为wi和vi，如果黑点是2，那么个数就是2^{vi。如果白点是2，那么个数是2}wi。那么这个连通分支的就是这两个数的和，整个图的就是各个连通分支的数的乘积。。

由于这是多组输入，vector要清零。
不要用memset，对数组都做了一个遍，会TLE。
代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#define ll long long
#define mod 998244353
using namespace std;

const int maxx=3e5+10;
vector<int >p[maxx];
int color[maxx];
int cnt1=0;
int cnt0=0;
int n,m;
int flag;

ll qsm(ll a,ll b)//快速幂
{
	ll ans=1;
	while(b)
	{
		if(b%2) 
		ans=(ans*a)%mod;
		b/=2;
		a=(a*a)%mod;
	}
	return ans;
}

void init()
{
	for(int i=0;i<=n;i++) p[i].clear();
	for(int i=0;i<=n;i++) color[i]=0;
}

void dfs(int x,int c)
{
	if(c==1) cnt1++;
	if(c==2) cnt0++;
	color[x]=c;
	for(int i=0;i<p[x].size();i++)
	{
		if(color[p[x][i]]==0) dfs(p[x][i],3-c);//3-c，如果是1，那么就变成了2，如果是2，就变成了1。如果是3，那么就变成了0，那样的话，就相当于没有遍历，以后偶还是会遍历到的。。
		else if(color[p[x][i]]==c)//有奇数环
		{
			flag=0;
			return ;
		}
	}
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			p[a].push_back(b);
			p[b].push_back(a);
		}
		flag=1;
		ll ans=1;
		for(int i=1;i<=n;i++)
		{
			if(color[i]==0)
			{
				cnt1=0;
				cnt0=0;
				dfs(i,1);
				if(!flag) break;
				ans=(ans*(qsm(2,cnt1)%mod+qsm(2,cnt0)%mod)%mod)%mod;
			}
		}
		if(!flag) printf("0\n");
		else printf("%I64d\n",ans%mod);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

努力加油a啊，(^o)/~