UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206770#3693. 染色 1one_zero_four_zero1001992ms14724kbC++11814b2024-07-25 17:42:452024-07-25 20:02:15

answer

#include<bits/stdc++.h>
using namespace std;

int n, m;
int u, v;
long long ans = 1, mod = 998244353;
int col[200005];
vector<int> E[200005];

void dfs(int u, int c){
    col[u] = c;
    for (auto && i : E[u]){
        if (col[i] == col[u]){
            printf("0\n");
            exit(0);
        }
        if (col[i]) continue;
        dfs(i, 3 - c);
	}
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in","r",stdin);
    freopen("../data.out","w",stdout);
#endif

    scanf("%d %d", &n, &m);
    while (m --){;
        scanf("%d %d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
    }
    for (int i = 1; i <= n; i ++){
        if (col[i]) continue;
        dfs(i, 1);
        ans = (ans * 2) % mod;
    }
    printf("%lld\n", ans % mod);

    return 0;
}

Details

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

Test #1:

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

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

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: 2ms
memory: 5928kb

input:

20 4
1 2
2 3
3 4
4 1

output:

131072

result:

ok "131072"

Test #4:

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

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: 3ms
memory: 6660kb

input:

200000 0

output:

792253081

result:

ok "792253081"

Test #6:

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

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: 44ms
memory: 8772kb

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: 62ms
memory: 9532kb

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: 87ms
memory: 10148kb

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: 124ms
memory: 10664kb

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: 143ms
memory: 11360kb

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

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: 162ms
memory: 13160kb

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: 183ms
memory: 13988kb

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: 219ms
memory: 14724kb

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

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: 158ms
memory: 12296kb

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: 147ms
memory: 12308kb

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: 150ms
memory: 12328kb

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

input:

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

output:

0

result:

ok "0"