UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206780#3693. 染色 1Josephcheng100940ms9276kbC++11913b2024-07-25 17:48:502024-07-25 20:03:16

answer

#include<bits/stdc++.h>
#define N 200005
#define LL long long
#define MOD 998244353
using namespace std;

int n,m,u,v,pos,cnt,ans;
int head[N];
int color[N];
bool vis[N],op;

struct Edge
{
	int u,v,nxt;
}e[2*N];

void addEdge(int u,int v)
{
	e[++pos]={u,v,head[u]};
	head[u]=pos;
}

void dfs(int u,int col)
{
	vis[u]=true;
	color[u]=col;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!vis[v]) dfs(v,col^1);
		else if(color[v]!=col^1) op=true;
	}
}

LL qpow(LL x,LL y)
{
	if(y==1) return x;
	if(y==0) return 1;
	LL res=qpow(x,y/2)%MOD;
	res=(res*res)%MOD;
	if(y&1) res=(res*x)%MOD;
	return res%MOD;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		addEdge(u,v);
		addEdge(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]) dfs(i,0),cnt++;
	ans=qpow(2,cnt)%MOD;
	if(op) printf("0"),exit(0);
	printf("%lld",ans%MOD);
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1208kb

input:

20 10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

output:

1024

result:

ok "1024"

Test #2:

score: 5
Accepted
time: 0ms
memory: 1208kb

input:

20 33
6 9
16 12
10 15
13 19
17 18
3 5
14 10
18 6
12 5
14 3
20 11
5 7
11 10
20 15
11 3
20 16
9 8
16 3...

output:

2

result:

ok "2"

Test #3:

score: 5
Accepted
time: 0ms
memory: 1204kb

input:

20 4
1 2
2 3
3 4
4 1

output:

131072

result:

ok "131072"

Test #4:

score: 5
Accepted
time: 0ms
memory: 1196kb

input:

20 44
1 7
4 8
16 11
6 17
11 13
19 10
5 4
6 20
12 20
7 18
2 14
2 4
14 16
8 7
12 6
12 15
12 19
19 16
1...

output:

0

result:

ok "0"

Test #5:

score: 5
Accepted
time: 0ms
memory: 2184kb

input:

200000 0

output:

792253081

result:

ok "792253081"

Test #6:

score: 5
Accepted
time: 10ms
memory: 3420kb

input:

200000 20000
174989 72342
29431 82489
134989 16335
195898 6766
44379 166973
63575 179953
56568 25387...

output:

591782332

result:

ok "591782332"

Test #7:

score: 5
Accepted
time: 17ms
memory: 3892kb

input:

200000 40000
130141 81160
183643 55620
127442 59859
108045 119463
53388 131934
165208 164601
175718 ...

output:

342500594

result:

ok "342500594"

Test #8:

score: 5
Accepted
time: 25ms
memory: 4356kb

input:

200000 60000
171595 53259
39846 120035
194218 185176
199578 128587
109637 186890
61191 149114
13490 ...

output:

449711975

result:

ok "449711975"

Test #9:

score: 5
Accepted
time: 20ms
memory: 4824kb

input:

200000 80000
187748 73706
15086 125096
41903 104401
116412 136210
65816 36448
193171 181724
132712 1...

output:

488189483

result:

ok "488189483"

Test #10:

score: 5
Accepted
time: 55ms
memory: 5296kb

input:

200000 99999
82325 170581
135463 7992
6832 37354
182855 12267
22716 105436
193084 100744
23038 13949...

output:

78278423

result:

ok "78278423"

Test #11:

score: 5
Accepted
time: 52ms
memory: 5932kb

input:

200000 119999
6165 92447
96033 58454
123842 66763
165430 17518
10165 19222
81965 119810
139780 71394...

output:

252055733

result:

ok "252055733"

Test #12:

score: 5
Accepted
time: 67ms
memory: 6772kb

input:

200000 139998
82113 88641
95759 69269
8316 145629
47 53984
170614 123587
117656 184230
577 63209
111...

output:

462026080

result:

ok "462026080"

Test #13:

score: 5
Accepted
time: 71ms
memory: 7612kb

input:

200000 159998
66716 121827
80674 122443
43128 28295
21904 164099
155673 181760
65574 49206
9370 1037...

output:

269680017

result:

ok "269680017"

Test #14:

score: 5
Accepted
time: 78ms
memory: 8464kb

input:

200000 180000
38840 146514
83106 155855
95948 59635
2672 180633
46476 32494
17665 128504
39486 79516...

output:

965754317

result:

ok "965754317"

Test #15:

score: 5
Accepted
time: 87ms
memory: 9276kb

input:

200000 199999
74181 148298
172708 84122
128717 191784
145066 169886
97568 4822
41662 106531
155190 1...

output:

400146199

result:

ok "400146199"

Test #16:

score: 5
Accepted
time: 87ms
memory: 9260kb

input:

200000 199999
26174 152764
68298 125193
94893 95074
160078 127091
139840 76057
67459 51195
144214 16...

output:

0

result:

ok "0"

Test #17:

score: 5
Accepted
time: 92ms
memory: 9264kb

input:

200000 200000
49288 149508
16008 106916
154117 48928
185344 66024
110881 86068
108409 129286
3267 20...

output:

0

result:

ok "0"

Test #18:

score: 5
Accepted
time: 100ms
memory: 9268kb

input:

200000 199995
76537 52199
163353 74374
6227 51113
126883 46291
180849 124164
75589 93348
168981 8843...

output:

0

result:

ok "0"

Test #19:

score: 5
Accepted
time: 85ms
memory: 9248kb

input:

200000 199998
105389 154107
18088 61057
11136 103748
6361 47540
18612 173030
72837 73696
3808 138264...

output:

0

result:

ok "0"

Test #20:

score: 5
Accepted
time: 94ms
memory: 9248kb

input:

200000 199999
167802 125259
194020 186636
11474 133555
22188 83709
14389 67107
198734 53893
21509 33...

output:

0

result:

ok "0"