ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206780 | #3693. 染色 1 | Josephcheng | 100 | 940ms | 9276kb | C++11 | 913b | 2024-07-25 17:48:50 | 2024-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"