ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206776 | #3693. 染色 1 | 1024i | 100 | 2072ms | 14756kb | C++11 | 1.4kb | 2024-07-25 17:46:24 | 2024-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
Details
小提示:点击横条可展开更详细的信息
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"