QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340605#7313. Connected Spanning SubgraphSKHUOAC ✓271ms15908kbC++14840b2024-02-29 10:40:462024-02-29 10:40:47

Judging History

你现在查看的是最新测评结果

  • [2024-02-29 10:40:47]
  • 评测
  • 测评结果:AC
  • 用时:271ms
  • 内存:15908kb
  • [2024-02-29 10:40:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int col[N];
vector<int> e[N];

bool dfs(int u, int c) {
  col[u] = c;
  bool res = 1;
  for (auto v : e[u]) {
    if (col[v] == !c) continue;
    if (col[v] == c) return 0;
    res &= dfs(v, !c);
    if (!res) return 0;
  }
  return 1;
}

void solve() {
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].emplace_back(v), e[v].emplace_back(u);
  }
  
  memset(col, -1, sizeof(col));
  if (!dfs(1, 0)) {
    cout << "0\n";
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (col[i] == -1) {
      cout << "0\n";
      return;
    }
  }
  cout << "1\n";
}

int main() {
  
  while (cin >> n >> m) {
    solve();
    for (int i = 1; i <= n; i++) e[i].clear();
  }
  
  return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9024kb

input:

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

output:

1
1
0

result:

ok 3 number(s): "1 1 0"

Test #2:

score: 0
Accepted
time: 271ms
memory: 9076kb

input:

11 14
7 5
2 6
10 3
8 2
8 11
4 6
11 1
5 6
1 10
5 4
5 2
4 3
1 7
8 9
4 4
1 4
2 4
2 3
3 4
10 18
9 10
1 8
10 6
3 5
4 10
10 8
3 1
2 6
4 2
8 2
3 2
5 9
6 5
5 4
8 7
9 7
10 3
1 4
3 2
3 1
2 1
15 27
10 2
3 12
12 6
8 4
5 8
6 9
9 7
4 9
1 6
3 14
13 8
2 12
2 6
8 11
4 11
14 1
15 5
13 11
1 12
15 2
11 15
12 11
15 14
8...

output:

0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
0
1
1
0
1
1
0
0
1
1
0
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
0
1
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
...

result:

ok 20000 numbers

Test #3:

score: 0
Accepted
time: 93ms
memory: 9096kb

input:

55 94
5 23
13 3
5 55
30 41
45 44
54 34
8 13
41 36
48 53
20 55
34 2
42 2
36 45
50 28
18 7
39 35
26 16
31 54
39 1
44 2
52 33
36 55
29 46
40 11
4 9
30 4
24 27
17 26
24 26
26 3
21 49
15 24
30 48
35 22
54 28
23 48
51 49
44 47
9 40
38 11
33 10
36 53
25 20
20 22
42 43
28 31
20 13
12 47
10 1
28 1
19 18
28 9...

output:

0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
0
0
1
1
1
0
0
1
1
1
1
1
0
0
0
1
1
0
1
1
0
0
0
0
1
1
1
1
0
1
0
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
0
0
0
1
1
1
0
1
1
0
0
1
1
0
1
1
1
0
0
1
0
1
0
1
1
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
1
0
0
1
0
1
1
0
0
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
1
1
0
...

result:

ok 4000 numbers

Test #4:

score: 0
Accepted
time: 103ms
memory: 15284kb

input:

196610 200000
163557 46167
70110 195039
189296 55169
106600 109232
146394 167208
137086 164692
35965 104965
133032 14094
49500 133762
45504 158534
136509 113879
29982 20540
143526 32564
110528 178476
139292 128353
154108 113236
18731 137448
7 75423
24744 92890
8773 163226
176473 161156
100983 132320...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 110ms
memory: 15120kb

input:

131075 199997
5177 37114
50807 21669
6711 119171
75364 90414
17847 110220
14720 107598
79456 95652
64770 105847
48134 63600
72584 76166
125642 78566
90325 31526
60773 10916
51311 95564
3446 82033
128895 98632
7503 128851
59235 61948
49770 126624
72505 92766
68572 12453
20745 48100
105725 17721
77708...

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 88ms
memory: 13296kb

input:

44297 199976
41208 6854
4991 43221
14769 42546
28158 18789
41370 3609
35775 1406
6542 32951
8136 43069
11707 12587
40718 11224
26458 34769
14045 9503
24602 15214
32096 1966
23989 25577
3953 42820
9034 32608
43125 858
25462 25330
18547 2286
19652 12154
38846 17652
15723 34648
160 36958
42205 34836
17...

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 103ms
memory: 15788kb

input:

175496 199999
156971 52651
125486 132949
24025 174872
49902 56334
152437 130374
104538 113871
26879 155760
7077 25353
127464 78011
32879 156328
111219 4864
103949 105338
26053 60225
20638 20126
61605 92380
115045 163982
9554 90486
23758 43052
149950 3012
127469 26557
163250 23711
29937 161570
24682 ...

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 90ms
memory: 13120kb

input:

92685 199995
44763 42807
7211 42018
653 5788
10711 32143
80630 68773
41899 21187
1332 42588
55834 49107
59570 7965
18910 69007
19314 86406
41819 393
8159 73573
79926 66152
22772 87543
62718 36677
85357 85983
77571 35602
61508 9093
2527 83154
59611 57919
46111 88290
57960 1459
46753 4831
44240 7622
1...

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 77ms
memory: 12096kb

input:

15438 199664
1757 1776
1781 7337
6809 13352
13008 5024
6839 2465
8707 4853
6383 11904
13876 5994
10707 11674
10454 8181
7267 15335
5410 11686
6659 10762
2163 7338
13925 12500
244 6399
13282 14856
7095 2973
689 4668
4814 1669
13352 2886
5787 7414
6853 1698
7375 8178
13814 11175
12042 13957
7288 7327
...

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 106ms
memory: 13776kb

input:

135408 199999
98546 110442
13298 97892
73909 82964
131859 101372
76595 40993
100927 40454
60451 106927
133526 111759
10322 67619
6248 64184
16023 41668
39806 74070
97774 53212
78879 1885
6129 94560
95191 124164
51759 82745
99372 42819
77411 103506
94362 117150
117818 7686
101499 37774
88522 90777
67...

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 86ms
memory: 12636kb

input:

65540 199995
64609 57230
41927 1718
60150 15826
30856 36610
640 41250
46351 22618
37920 49954
53705 7984
60685 62319
51193 41818
18713 11033
48437 40851
24642 16571
131 53217
27322 4793
53316 18735
1438 37993
11533 30442
37559 53446
10467 8861
58158 4149
37685 28232
51846 31887
39525 44214
5515 2668...

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 118ms
memory: 15908kb

input:

175349 200000
14630 104033
160153 103487
111828 135414
150141 86091
85155 79014
154017 22286
150867 164160
158067 19526
136991 127117
118445 63204
16817 107629
168786 15850
93485 152748
161751 11645
172216 168595
26298 101852
86677 58771
114691 75235
113741 77165
141989 64406
36902 133568
18478 1492...

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 97ms
memory: 13780kb

input:

65540 199980
11840 8682
5429 48197
51700 9235
42072 64457
9402 26549
31913 62498
41483 51416
22353 23535
52975 35103
40283 35762
28823 49993
63031 11759
50908 63119
19231 39051
10191 44468
30048 31993
35066 33139
58483 61997
57496 57955
27409 52257
23302 28937
5823 9672
11988 7811
20133 19805
18749 ...

output:

1

result:

ok 1 number(s): "1"

Extra Test:

score: 0
Extra Test Passed