QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382346#999. 边双连通分量IsrothyAC ✓87ms29104kbC++232.3kb2024-04-08 12:49:382024-04-08 12:49:39

Judging History

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

  • [2024-04-08 12:49:39]
  • 评测
  • 测评结果:AC
  • 用时:87ms
  • 内存:29104kb
  • [2024-04-08 12:49:38]
  • 提交

answer

#include <cstdio>
#include <span>
#include <vector>
struct TarjanEcc {
    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int> dfn, low;
    std::vector<bool> is_bridge;
    std::vector<std::vector<int>> eccs;
    int dfs_clock;
    TarjanEcc(std::span<std::pair<int, int>> edges, int n)
        : adj(n + 1), dfn(n + 1), low(n + 1), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
        for (int i = 0; i < edges.size(); ++i) {
            auto [u, v] = edges[i];
            adj[u].emplace_back(v, i);
            adj[v].emplace_back(u, i);
        }
        for (int u = 1; u <= n; ++u) {
            if (!dfn[u]) {
                find_bridges(u, -1);
            }
        }
        std::vector<bool> visited(n + 1);
        for (int u = 1; u <= n; ++u) {
            if (!visited[u]) {
                std::vector<int> q;
                q.emplace_back(u);
                visited[u] = true;
                for (int ptr = 0; ptr < q.size(); ++ptr) {
                    auto v = q[ptr];
                    for (auto [w, id]: adj[v]) {
                        if (!is_bridge[id] && !visited[w]) {
                            visited[w] = true;
                            q.push_back(w);
                        }
                    }
                }
                eccs.emplace_back(std::move(q));
            }
        }
    }

private:
    void find_bridges(int u, int prev) {
        dfn[u] = low[u] = ++dfs_clock;
        for (auto [v, id]: adj[u]) {
            if (prev == id) {
                continue;
            }
            if (!dfn[v]) {
                find_bridges(v, id);
                low[u] = std::min(low[u], low[v]);
                is_bridge[id] = dfn[u] < low[v];
            } else {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    std::vector<std::pair<int, int>> edges(m);
    for (auto &[u, v]: edges) {
        scanf("%d%d", &u, &v);
        ++u;
        ++v;
    }
    auto eccs = TarjanEcc(edges, n).eccs;
    printf("%zu\n", eccs.size());
    for (const auto &ecc: eccs) {
        printf("%zu", ecc.size());
        for (auto u: ecc) {
            printf(" %d", u - 1);
        }
        puts("");
    }

    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 0 2 1 3

result:

ok OK

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 0 9 11 1 5 4
4 2 10 12 3
3 6 7 8

result:

ok OK

Test #3:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

2 2
0 1
1 0

output:

1
2 0 1

result:

ok OK

Test #4:

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

input:

200000 200000
127668 148778
77100 11865
85144 199231
39485 84917
102044 187263
130204 174776
26220 198288
162188 12078
92196 146334
120537 38083
150353 160479
18707 6545
101149 25450
62271 9177
38892 6454
11709 191939
89247 145109
140599 121858
197410 148980
55975 169098
128576 59852
68224 182347
89...

output:

105340
1 0
94661 1 196297 9259 81390 89202 199857 78223 152391 122336 78748 111501 158266 24036 32932 8316 1190 163544 22352 133465 61251 154506 26312 73742 26893 51025 109513 105960 117898 104884 196087 56255 163996 89186 77981 33913 187272 111924 163058 10423 70690 174526 87370 148347 112830 14052...

result:

ok OK

Test #5:

score: 0
Accepted
time: 87ms
memory: 28960kb

input:

200000 200000
150762 148756
172967 108322
69862 125085
84513 111056
141009 156725
36311 103205
31879 79919
62895 63377
21697 115522
161610 160423
113104 10277
106927 168428
136657 198931
52292 164110
149020 7038
115111 112823
35584 124385
45429 191603
96444 30523
195578 149089
160105 58103
139792 27...

output:

104955
95046 0 149495 82146 128417 52721 9447 107825 4627 126113 156857 190891 118745 30886 9684 163 117099 195843 111407 168726 113246 102263 164233 114519 32255 115349 69732 86726 101233 176543 25257 187174 159166 71440 71603 155403 61449 120213 41044 136949 177666 167848 193277 180803 137742 8421...

result:

ok OK

Test #6:

score: 0
Accepted
time: 85ms
memory: 29028kb

input:

200000 200000
53335 120202
193029 92221
8244 61648
50176 7825
97274 91479
85438 76999
26861 80116
162826 198446
160509 95916
143190 116619
121254 192931
121545 132273
149400 91882
97032 5048
179008 82221
187475 70697
159074 65868
158744 94466
120006 170635
36429 162768
61114 17876
131798 188508
1080...

output:

105649
94350 0 195600 4357 133179 59178 75624 123762 79357 134520 189046 88724 42464 160417 103385 17791 167432 156908 28848 184508 187886 93969 159664 103625 16640 68373 177023 68521 15192 112109 176927 71367 62388 177087 110630 23044 48338 47125 78814 6422 46536 132749 5902 18527 45143 25129 28461...

result:

ok OK

Test #7:

score: 0
Accepted
time: 64ms
memory: 20264kb

input:

127669 148779
124640 77100
11865 117450
85144 68159
104241 39485
76372 84917
102044 56191
43704 26220
67216 31116
75749 123504
12078 92196
70006 15262
100591 74552
120537 38083
19281 29407
18707 6545
101149 25450
62271 9177
38892 6454
11709 119710
60867 89247
14037 9527
121858 66338
112298 81804
795...

output:

51131
76537 0 33641 110791 110556 105049 73038 112503 84038 17626 10978 95615 34815 117633 119035 49978 46971 21370 67212 98517 66319 53531 17113 46862 78172 78041 58319 47898 31255 57318 58168 48445 30038 13687 97176 126292 86433 37973 33281 11636 8497 41953 98572 16867 27840 48688 54207 89275 2522...

result:

ok OK

Test #8:

score: 0
Accepted
time: 72ms
memory: 23220kb

input:

150763 148757
108322 69862
125085 84513
111056 141009
36311 103205
31879 79919
62895 63377
21697 115522
113104 10277
106927 136657
52292 149020
7038 115111
112823 35584
124385 45429
96444 30523
149089 58103
139792 27250
15883 109949
69372 132387
141930 113408
65522 128254
138198 141969
42522 92075
1...

output:

81019
69744 0 149495 88101 41333 52721 61353 18385 25401 36516 66625 61467 80090 32542 57116 76580 138898 106306 136221 144801 86518 76958 107942 97726 42061 55617 112526 55913 51590 81203 38890 44372 136442 17643 30268 72250 124258 131875 35667 120783 35419 37419 15069 29245 35412 84425 133196 3379...

result:

ok OK

Test #9:

score: 0
Accepted
time: 38ms
memory: 13128kb

input:

53336 120203
26685 8244
50176 7825
31738 24370
25943 19902
11463 26861
29977 26309
14580 31754
1838 29437
30380 12118
51083 31633
1201 18328
26346 5295
48935 19027
31496 19906
41783 5048
47936 16685
5161 34107
15907 28002
332 27672
28930 39563
36429 31696
17876 726
42526 21682
35319 8727
17974 25252...

output:

3392
49945 0 2478 32623 5394 42870 39419 47233 15492 9420 12826 35320 14679 31171 50935 9537 26456 34641 23433 29165 2736 5180 3612 3855 3155 16487 34802 52211 48662 27489 32378 45573 14140 6082 36724 17205 581 17234 2018 37440 27372 36465 25815 21858 25196 1641 20865 42493 50193 41304 540 5561 301 ...

result:

ok OK

Test #10:

score: 0
Accepted
time: 17ms
memory: 7252kb

input:

17707 71661
1354 3272
13699 17294
16733 9246
14993 5758
7252 2983
3813 6121
10450 14069
8088 11201
857 4420
12788 2032
11938 1465
10322 15171
14688 1857
2309 2742
2013 13200
14142 16319
10541 1922
10368 1516
7994 9092
3327 5166
13484 2876
15472 13522
15622 13479
3361 15314
15464 14974
17637 7535
435...

output:

75
16444 0 14055 6372 12266 13517 8659 8959 13373 12781 9257 345 13180 6531 17530 12916 6145 14409 7249 16451 3868 16303 841 15071 8699 430 4451 1184 9515 7340 14064 3356 10528 9204 4164 10036 4579 2473 11082 16807 15864 11693 2682 437 11641 5492 2842 1136 6951 15543 10584 14265 9854 1227 10858 9899...

result:

ok OK

Test #11:

score: 0
Accepted
time: 0ms
memory: 4608kb

input:

4294 17517
1175 3250
314 389
4272 3633
2938 1831
1307 2818
3321 347
1205 1428
2354 1478
1003 3898
1587 3443
1122 1512
2512 3995
348 3280
2064 1022
1834 2958
4281 1863
689 3613
2115 3708
1645 1488
1601 4181
916 4276
128 2626
4147 2868
87 1411
1802 1451
1254 2010
2936 3120
1065 277
1121 3284
3655 2849...

output:

29
3031 0 4272 3240 3490 2081 1909 3942 1567 2837 2364 452 1326 3633 10 3767 730 4044 286 341 4147 4084 717 133 3420 3332 1339 2208 4268 291 2356 3051 327 3193 2030 2306 2894 1791 3664 1077 3418 2852 757 3466 2710 2798 1863 2577 1720 2927 594 3138 1705 937 3130 3760 4239 1582 3493 1669 1030 2148 156...

result:

ok OK

Test #12:

score: 0
Accepted
time: 26ms
memory: 8548kb

input:

26686 105813
14774 5315
22701 21346
1398 13888
18566 18745
22298 6181
21347 10653
16500 23768
2329 5818
17512 16769
25519 338
12580 3064
19467 21665
3978 13202
23556 25178
195 9695
1472 13111
22925 24074
3026 13281
17666 14469
22007 18680
4159 13152
20431 23814
6671 10788
24433 13211
9794 12608
3264...

output:

137
11036 0 18068 3993 1138 21038 1664 22550 10881 23349 25741 24322 25764 23075 12221 6633 25923 18120 20851 10526 9161 3283 13523 3850 15514 13854 8228 17528 7963 18053 7932 21007 5890 20418 9596 7347 12223 25437 13022 21215 21928 25787 1376 23454 9256 14168 7934 490 6979 9549 10969 11689 1781 172...

result:

ok OK

Test #13:

score: 0
Accepted
time: 36ms
memory: 10244kb

input:

36033 148595
33366 22486
14414 23855
2694 30361
16352 31902
27993 2048
4707 31743
30610 12884
23278 27069
10529 20914
2030 30015
24554 15673
10184 29423
17825 20383
34077 1181
25518 26129
6355 8810
2857 21736
25108 34280
14992 24299
32649 20227
34529 10407
23194 29913
10451 319
34666 8904
30811 3003...

output:

150
7961 0 28838 33260 8383 17494 9626 35128 8630 10061 6558 9304 14101 10217 11304 25288 14882 18557 34548 11201 27889 3094 23765 9384 23468 9601 16503 4908 24171 16339 20675 19919 1496 2320 19550 22436 14267 35597 29899 7024 14093 17226 28729 27203 19382 5482 10087 13508 11097 502 35653 31468 3622...

result:

ok OK

Test #14:

score: 0
Accepted
time: 14ms
memory: 6524kb

input:

14868 57739
5724 2103
9214 3074
2269 531
3811 13162
5199 12632
6337 12078
12592 4977
3553 6975
5063 6622
1221 13056
4252 3705
7547 7879
1702 3685
4058 2503
7540 9423
4280 12228
574 6265
11876 2711
4805 7605
1468 4802
6921 1954
6350 2733
4429 5862
13549 14543
13809 5357
1509 11478
87 2676
6299 7060
1...

output:

80
5372 0 4278 458 196 5091 6407 8013 717 11573 8486 6825 4810 12590 6347 2745 10157 7758 9582 3339 7341 14798 6085 7569 5532 3853 13110 13845 5642 6154 6964 1733 9782 6357 6179 248 14784 9 2958 13201 12714 8618 6183 8367 14653 13171 11768 5761 5799 2914 3056 12879 5766 4986 9199 1862 2974 3280 1406...

result:

ok OK

Test #15:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

53 43
32 44
25 10
24 49
20 28
28 44
16 12
37 48
46 36
30 47
25 3
17 31
19 17
29 42
25 44
30 3
31 21
2 34
42 12
22 50
12 52
39 10
0 46
29 1
12 21
3 0
11 31
42 25
4 51
26 36
19 48
39 26
5 21
7 41
29 34
38 47
29 8
26 17
42 46
36 20
39 30
13 27
28 31
27 24

output:

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

result:

ok OK

Test #16:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

70 21
39 34
29 33
38 53
37 7
47 64
47 17
65 66
60 39
37 47
19 68
14 28
39 41
52 55
0 60
59 16
11 40
11 33
35 26
0 11
24 17
26 43

output:

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

result:

ok OK

Test #17:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

88 139
5 61
52 80
0 17
50 87
62 71
25 69
10 46
44 86
11 38
17 35
73 49
24 47
39 83
8 66
55 56
64 45
83 41
59 35
76 24
2 70
11 77
80 58
84 86
30 50
23 54
36 74
12 10
62 75
33 34
43 28
77 29
10 46
77 33
26 48
32 38
52 79
15 30
25 57
86 0
46 75
81 60
35 83
66 87
25 86
19 85
9 38
15 64
59 82
0 53
40 66
...

output:

16
73 0 17 86 72 35 70 56 44 84 25 66 20 59 83 50 27 2 80 48 33 49 55 71 67 58 69 57 81 8 87 40 15 61 10 39 41 30 36 62 5 21 7 52 26 65 79 77 73 6 1 75 28 60 43 46 4 29 64 23 22 85 11 3 37 9 78 76 14 24 63 19 38 32
1 12
1 13
1 16
1 18
1 31
1 34
1 42
1 45
1 47
1 51
1 53
1 54
1 68
1 74
1 82

result:

ok OK

Test #18:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

53 185
48 40
23 7
45 7
6 42
13 6
45 1
18 28
47 14
11 15
27 9
50 44
23 47
20 27
18 19
2 19
18 49
32 49
9 12
11 0
32 49
22 14
8 48
41 28
30 43
4 21
7 22
28 30
17 11
19 30
44 7
46 8
50 45
35 48
29 47
4 26
16 39
37 25
38 12
19 52
28 41
23 31
33 34
6 15
44 24
0 6
26 22
49 43
4 31
20 38
43 39
41 39
51 40
...

output:

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

result:

ok OK

Test #19:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

70 252
63 36
64 48
26 34
43 37
30 53
67 64
26 19
25 54
28 44
52 60
4 22
43 48
14 48
12 50
37 23
28 40
48 54
60 23
43 46
7 5
29 39
5 13
57 60
1 23
33 8
59 39
3 29
5 8
34 11
44 40
39 19
40 17
42 48
39 19
49 46
0 48
46 45
57 67
43 60
56 59
32 42
6 54
56 69
23 43
38 65
66 24
0 64
16 10
23 1
4 16
37 49
5...

output:

1
70 0 48 64 57 67 15 52 45 42 43 14 54 49 6 60 46 23 22 25 51 32 37 1 5 4 66 36 65 7 13 8 59 26 33 2 9 29 34 39 16 28 44 24 40 17 47 63 10 38 31 62 12 11 68 21 69 56 53 61 50 19 35 30 55 3 41 27 58 20 18

result:

ok OK

Test #20:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

88 390
74 40
14 37
44 66
7 49
12 4
39 48
56 76
46 40
80 30
5 39
52 0
40 79
0 11
34 41
43 80
54 62
61 41
54 37
31 81
59 66
23 59
47 84
16 85
68 29
31 63
4 55
27 5
26 68
14 84
16 34
82 16
62 54
46 15
65 63
58 83
5 36
67 19
65 42
35 25
82 73
55 59
28 36
22 38
46 79
61 34
51 40
69 42
36 5
26 38
86 14
22...

output:

3
76 0 52 11 75 45 49 79 7 24 86 50 40 46 15 74 17 6 64 14 28 51 18 82 37 84 62 47 54 29 70 21 3 58 83 16 73 61 57 41 34 10 78 68 38 19 85 80 66 72 30 1 69 26 22 67 32 25 87 43 2 44 59 53 12 42 8 65 31 63 13 81 35 55 71 4 23
6 5 39 27 36 48 60
6 9 56 77 76 20 33

result:

ok OK