UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206777#3693. 染色 1three_zero301002054ms14752kbC++11751b2024-07-25 17:46:292024-07-25 20:02:58

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
int n,m,a,b;
const int N=2e5+2;
vector<int> vec[N];
int colour[N];
ll ans=1;
bool f=0;
void dfs(int u,int c){
	if(f)return ;
	colour[u]=c;
	if(vec[u].empty()){
		return ;
	}
	for(auto v:vec[u]){
		if(colour[v]==0){
			dfs(v,3-c);
		}
		else if(c==colour[v]){
			f=1;
			return ;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		if(colour[i]==0){
			dfs(i,1);
			if(f){
				cout<<0<<endl;
				return 0;
			}
			ans=ans*2;
			ans%=MOD;
		}
	}
	cout<<ans%MOD<<endl;
	return 0;
}

详细

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

Test #1:

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

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: 4ms
memory: 5948kb

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: 4ms
memory: 5948kb

input:

20 4
1 2
2 3
3 4
4 1

output:

131072

result:

ok "131072"

Test #4:

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

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: 6716kb

input:

200000 0

output:

792253081

result:

ok "792253081"

Test #6:

score: 5
Accepted
time: 21ms
memory: 7864kb

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: 33ms
memory: 8796kb

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: 54ms
memory: 9556kb

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: 63ms
memory: 10172kb

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: 106ms
memory: 10692kb

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: 126ms
memory: 11384kb

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: 164ms
memory: 12280kb

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: 154ms
memory: 13192kb

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: 164ms
memory: 14012kb

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: 257ms
memory: 14752kb

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: 185ms
memory: 12356kb

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: 166ms
memory: 12320kb

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: 185ms
memory: 12348kb

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: 184ms
memory: 12356kb

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: 184ms
memory: 12384kb

input:

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

output:

0

result:

ok "0"