QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#382346 | #999. 边双连通分量 | Isrothy | AC ✓ | 87ms | 29104kb | C++23 | 2.3kb | 2024-04-08 12:49:38 | 2024-04-08 12:49:39 |
Judging History
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