QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#676559 | #999. 边双连通分量 | Poetry# | AC ✓ | 73ms | 27768kb | C++23 | 1.5kb | 2024-10-25 22:01:43 | 2024-10-25 22:01:44 |
Judging History
answer
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
constexpr int N = 1E6 + 5;
int n, m, tot = 1, head[N], to[N], next[N];
void addEdge(int u, int v) {
to[++tot] = v;
next[tot] = head[u];
head[u] = tot;
}
void addEdges(int u, int v) {
addEdge(u, v);
addEdge(v, u);
}
int dfn[N], low[N], cnt;
bool bridge[N];
void tarjan(int x, int fr) {
dfn[x] = low[x] = ++cnt;
for (int i = head[x]; i; i = next[i]) {
int y = to[i];
if (!dfn[y]) {
tarjan(y, i);
low[x] = std::min(low[x], low[y]);
if (dfn[y] == low[y]) {
bridge[i] = bridge[i ^ 1] = 1;
}
} else if ((i ^ 1) != fr)
low[x] = std::min(low[x], dfn[y]);
}
}
int bel[N];
std::vector<int> vec[N];
void divide(int x, int id) {
bel[x] = id;
vec[id].push_back(x);
for (int i = head[x]; i; i = next[i]) {
int y = to[i];
if (bel[y] || bridge[i]) continue;
divide(y, id);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
std::cin >> u >> v;
++u, ++v;
addEdges(u, v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) tarjan(i, 0);
}
cnt = 0;
for (int i = 1; i <= n; ++i) {
if (!bel[i]) {
divide(i, ++cnt);
}
}
std::cout << cnt << "\n";
for (int i = 1; i <= cnt; ++i) {
std::cout << vec[i].size() << " ";
for (auto x : vec[i]) {
std::cout << x - 1 << " \n"[x == vec[i].back()];
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7804kb
input:
4 5 0 2 0 1 3 0 2 1 2 3
output:
1 4 0 3 2 1
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 9784kb
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 11 4 5 9 1 4 2 3 10 12 3 6 8 7
result:
ok OK
Test #3:
score: 0
Accepted
time: 2ms
memory: 7736kb
input:
2 2 0 1 1 0
output:
1 2 0 1
result:
ok OK
Test #4:
score: 0
Accepted
time: 73ms
memory: 26136kb
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 81390 152391 22352 89186 45552 120699 190664 62030 77594 184747 153510 130907 109651 111583 103836 83676 76270 74513 24169 190 34772 62656 165492 44029 100847 198281 172345 50988 157417 81369 143303 29039 175495 145757 150280 96757 63227 90612 82632 56020 132501 97095 71772 52063 ...
result:
ok OK
Test #5:
score: 0
Accepted
time: 71ms
memory: 27376kb
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 52721 190891 164233 136949 3012 153103 38758 37445 43103 137815 60121 74400 150650 6405 52869 39525 43994 79195 144942 80162 7806 105725 189293 36887 65604 69454 44788 43317 161381 179884 64239 114320 157747 187161 156795 173640 153523 40292 107734 14721 119087 171338 105102 4598 2535...
result:
ok OK
Test #6:
score: 0
Accepted
time: 55ms
memory: 27768kb
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 133179 189046 103625 132225 173468 40175 65049 12608 15331 39384 57106 138749 117594 143994 46712 36920 9490 19692 38801 22086 166241 70241 122125 147422 187045 195765 169167 94499 128189 52661 93757 10592 67354 4606 53731 62621 56872 73283 65932 181820 184939 140936 162172 27489 1088...
result:
ok OK
Test #7:
score: 0
Accepted
time: 39ms
memory: 18776kb
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 110791 73038 34815 58319 102824 45525 59421 108995 65318 111411 36280 89008 35818 12542 42649 727 70138 15213 44392 37142 115705 84532 39441 117947 43496 21456 61872 56403 51212 45177 23627 125455 115904 116381 124702 71453 99722 63914 19723 52842 59529 100187 83962 47122 117402 28214 ...
result:
ok OK
Test #8:
score: 0
Accepted
time: 52ms
memory: 23976kb
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 52721 61467 97726 42461 31420 40158 101554 46452 61719 42971 135893 24809 109158 111070 28061 35298 115630 6917 19449 55041 90515 76393 126762 141171 112245 97324 44551 14188 104013 15578 38336 94608 70255 121170 88038 141421 63791 9643 149312 116429 67699 121949 132925 109789 132259 1...
result:
ok OK
Test #9:
score: 0
Accepted
time: 21ms
memory: 16200kb
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 39419 45573 44086 27683 6798 47654 7911 11797 14814 11922 1083 47995 15924 43946 30439 3159 47035 9478 31661 563 52479 22224 37105 15709 44346 33664 47832 13783 51741 45477 49618 28721 11377 16454 41336 5065 31167 22304 49187 39267 20303 17985 30984 47710 46283 22769 44664 23591 16834 2...
result:
ok OK
Test #10:
score: 0
Accepted
time: 9ms
memory: 14792kb
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 13373 10861 4635 11171 14234 12358 16807 6688 11695 2537 11523 6402 1851 925 9635 7519 2882 9895 7173 4192 9179 6263 12412 14220 17609 14227 6951 10078 8900 8939 3733 8887 16184 7340 9872 11730 7241 3943 7865 12881 17589 5144 7851 6048 13072 2867 10634 786 10036 12266 2842 11957 13552 440...
result:
ok OK
Test #11:
score: 0
Accepted
time: 2ms
memory: 8008kb
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 1326 1032 1925 3799 3819 2549 4098 2738 3702 3760 2850 513 3189 798 330 2145 2623 2554 2955 2829 937 4069 18 413 900 3030 594 2208 2390 789 2591 3051 2228 2149 4239 1137 2427 64 1287 1355 2710 3420 2364 2868 2030 3922 1830 1720 3138 2148 27 2802 1077 1395 142 4063 3316 1622 2307 4147 2295 ...
result:
ok OK
Test #12:
score: 0
Accepted
time: 19ms
memory: 11000kb
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 10881 7203 18541 5805 25311 21546 26664 21759 6341 11935 1720 19359 16326 24573 5312 2788 25557 25479 13044 14565 16522 4866 9970 17586 10402 19910 13142 15342 18045 7663 13539 15514 13741 18142 14538 9169 713 14675 21094 8982 3960 21050 12896 12707 23068 13022 4164 10810 25923 18068 663...
result:
ok OK
Test #13:
score: 0
Accepted
time: 23ms
memory: 15144kb
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 8630 4929 27050 9220 14736 4117 4908 10947 6498 27469 13587 36031 29899 29576 11510 2957 12223 22436 8383 19919 3453 24244 32110 27377 32231 31035 1345 17226 4653 5198 18063 28991 4471 20808 3752 35869 9601 19051 606 26247 21846 502 32977 35713 23917 24526 7533 26226 12962 1218 3514 16339...
result:
ok OK
Test #14:
score: 0
Accepted
time: 10ms
memory: 8464kb
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 4810 11106 14440 5315 6482 3882 14234 1406 2596 12457 5415 14614 13419 12879 5091 5766 6154 6179 6825 13088 14653 9582 10999 6951 5579 1896 6085 11330 6148 7333 2993 11235 8013 13171 4061 6046 7341 4278 5532 2676 10234 8135 2914 6614 5761 2380 14004 1091 6258 10301 11484 3341 1472 3522 117...
result:
ok OK
Test #15:
score: 0
Accepted
time: 2ms
memory: 9808kb
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 3 30 39 26 17 31 28 44 25 42 46 36 20 12 21 10 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: 2ms
memory: 7824kb
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: 9868kb
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 72 20 61 57 28 37 5 1 55 56 17 70 49 6 9 7 2 21 33 73 77 14 22 41 23 60 81 25 86 66 15 48 79 39 83 35 27 36 11 38 85 30 50 87 52 78 3 62 71 75 4 8 46 10 59 24 76 32 65 80 26 58 44 64 29 19 63 69 40 84 67 43 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: 9828kb
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 8 17 13 42 9 40 11 15 6 38 27 48 35 46 10 51 3 20 12 16 1 24 21 44 47 22 4 45 31 14 29 50 5 26 7 23 17 2 43 18 25 49 52 39 36 19 28 34 37 41 16 30 33 32
result:
ok OK
Test #19:
score: 0
Accepted
time: 2ms
memory: 7748kb
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 52 25 32 51 54 14 43 45 49 48 67 22 65 31 44 17 38 55 61 8 53 41 56 62 2 12 33 5 39 50 29 59 11 7 35 30 18 21 26 68 9 13 69 19 34 3 6 60 64 15 42 23 57 1 37 46 66 47 24 10 36 63 16 4 28 40 27 58 20
result:
ok OK
Test #20:
score: 0
Accepted
time: 2ms
memory: 9788kb
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 45 75 11 49 50 6 64 24 86 28 7 14 84 78 47 54 37 62 10 69 65 63 8 31 13 81 67 19 25 87 35 32 21 58 83 70 18 3 15 46 74 79 17 40 51 29 38 22 68 26 12 53 55 23 4 44 59 66 73 1 43 80 30 72 2 82 61 41 57 34 16 85 71 42 6 5 27 36 48 39 60 6 9 76 56 33 77 20
result:
ok OK