UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206776#3693. 染色 11024i1002072ms14756kbC++111.4kb2024-07-25 17:46:242024-07-25 20:02:48

answer

//1024i
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 2e5 + 5;
const int MOD = 998244353;

vector<int> graph[MAXN];
int color[MAXN];
int n, m;

bool dfs(int u, int c) {
    color[u] = c;
    for (int v : graph[u]) {
        if (color[v] == c) return false;
        if (color[v] == 0 && !dfs(v, 3-c)) return false;
    }
    return true;
}

bool is_bipartite() {
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && !dfs(i, 1)) {
            return false;
        }
    }
    return true;
}

int count_components() {
    int count = 0;
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0) {
            dfs(i, 1);
            count++;
        }
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    if (!is_bipartite()) {
        cout << 0 << endl;
    } else {
        int components = count_components();
        int result = 1;
        for (int i = 0; i < components; i++) {
            result = (result * 2) % MOD;
        }
        cout << result << endl;
    }
    
    return 0;
}
//1024i

详细

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

Test #1:

score: 5
Accepted
time: 4ms
memory: 6716kb

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

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

input:

20 4
1 2
2 3
3 4
4 1

output:

131072

result:

ok "131072"

Test #4:

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

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: 9ms
memory: 6716kb

input:

200000 0

output:

792253081

result:

ok "792253081"

Test #6:

score: 5
Accepted
time: 23ms
memory: 7868kb

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: 50ms
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: 77ms
memory: 9560kb

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: 85ms
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: 127ms
memory: 10696kb

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: 153ms
memory: 11380kb

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: 155ms
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: 190ms
memory: 13188kb

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: 202ms
memory: 14024kb

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: 188ms
memory: 14756kb

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: 149ms
memory: 12352kb

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: 172ms
memory: 12336kb

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: 160ms
memory: 12352kb

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: 168ms
memory: 12360kb

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: 160ms
memory: 12380kb

input:

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

output:

0

result:

ok "0"