ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206777 | #3693. 染色 1 | three_zero30 | 100 | 2054ms | 14752kb | C++11 | 751b | 2024-07-25 17:46:29 | 2024-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"