QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#92061 | #999. 边双连通分量 | DaBenZhongXiaSongKuaiDi# | AC ✓ | 277ms | 30100kb | C++20 | 1.3kb | 2023-03-30 10:06:45 | 2023-03-30 10:06:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)2e5+5;
int n,m,idx,tag,dfn[maxn],fr[maxn],to[maxn],val[maxn],vis[maxn]; vector<int> f[maxn],ans[maxn];
void dfs(int u){
dfn[u] = ++idx;
for(auto X:f[u]){
int nxt = fr[X]+to[X]-u;
if(!dfn[nxt]) dfs(nxt), vis[X] = 1;
}
}
void getans(int u,int pidx){
dfn[u] = ++idx;
for(auto X:f[u]){
int nxt = fr[X]+to[X]-u;
if(!dfn[nxt]) getans(nxt,X), val[u] += val[nxt];
}
if(val[u]==0) vis[pidx] = 2;
}
void search(int u){
ans[tag].push_back(u);
dfn[u] = ++idx;
for(auto X:f[u])if(vis[X]==1){
int nxt = fr[X]+to[X]-u;
if(!dfn[nxt]) search(nxt);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int al=1;al<=m;al++)
scanf("%d%d",&fr[al],&to[al]), ++fr[al], ++to[al], f[fr[al]].push_back(al), f[to[al]].push_back(al);
for(int al=1;al<=n;al++)if(!dfn[al]) dfs(al);
for(int al=1;al<=m;al++)if(!vis[al]){
int A = fr[al], B = to[al];
if(dfn[A]>dfn[B]) swap(A,B);
--val[A], ++val[B];
}
for(int al=1;al<=n;al++) dfn[al] = 0;
idx = 0;
for(int al=1;al<=n;al++)if(!dfn[al]) getans(al,0);
for(int al=1;al<=n;al++) dfn[al] = 0;
idx = 0;
for(int al=1;al<=n;al++)if(!dfn[al]) ++tag, search(al);
printf("%d\n",tag);
for(int al=1;al<=tag;al++,printf("\n")){
printf("%d ",ans[al].size());
for(auto X:ans[al]) printf("%d ",X-1);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16076kb
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: 16660kb
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 1 5 4 11 4 2 10 3 12 3 6 7 8
result:
ok OK
Test #3:
score: 0
Accepted
time: 7ms
memory: 15784kb
input:
2 2 0 1 1 0
output:
1 2 0 1
result:
ok OK
Test #4:
score: 0
Accepted
time: 277ms
memory: 30100kb
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 89202 122336 133465 77981 162994 115216 110675 188403 114304 175554 115124 3943 167791 38352 181678 187268 110129 164600 35327 12304 19057 156171 42225 101821 25122 30631 174160 112712 161048 11306 127589 134003 162914 106803 95563 159644 1707 154949 137113 9621 189714 936...
result:
ok OK
Test #5:
score: 0
Accepted
time: 277ms
memory: 29848kb
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 9447 118745 114519 177666 67086 24973 7971 189045 31207 180001 151764 158809 135666 20089 157333 53907 82696 45056 176896 67 143336 42989 117925 18307 11843 107252 169827 96921 156075 166627 125002 109637 100499 145569 9748 131433 147791 58790 137930 86842 26129 195463 87475 17...
result:
ok OK
Test #6:
score: 0
Accepted
time: 224ms
memory: 29876kb
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 59178 88724 16640 31322 99678 110611 13868 163265 185876 181224 55997 153121 15046 165104 100529 69455 38552 68869 182539 114543 139558 133125 155251 63904 132084 127234 66618 31934 139610 82323 175302 12002 41949 31138 39449 77164 140667 44733 187480 44136 197262 177360 68540 ...
result:
ok OK
Test #7:
score: 0
Accepted
time: 156ms
memory: 25684kb
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 110556 112503 117633 47898 99898 36709 48114 74005 45833 37909 53196 36451 42543 115469 66349 56819 15502 122916 10770 41022 5220 114335 12175 27574 27058 62320 41737 70435 29621 46880 3572 96212 2530 53508 23747 76799 47322 110321 7137 47122 83498 68211 109886 73969 39098 76425 ...
result:
ok OK
Test #8:
score: 0
Accepted
time: 178ms
memory: 26424kb
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 61353 80090 42061 87619 29857 141305 93436 69553 29234 79220 46125 148484 37153 93416 74405 135927 41961 119716 84189 50071 72343 55678 107755 110054 76382 113745 127836 51210 10352 45902 42020 56616 46449 22768 144097 114294 147399 145776 17526 109021 14611 95857 103490 106571 ...
result:
ok OK
Test #9:
score: 0
Accepted
time: 75ms
memory: 21264kb
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 47233 14140 23050 19096 46542 51576 51860 36054 42995 33074 3906 6371 16835 47701 46003 3024 28128 30174 5646 12535 10452 9353 34005 19739 34181 31015 51201 46727 25097 15482 42660 30926 49673 12887 42453 18792 50156 24694 13798 37460 17482 10427 32520 50422 26610 22490 13605 35805...
result:
ok OK
Test #10:
score: 0
Accepted
time: 31ms
memory: 17292kb
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 12781 7241 9236 7551 14715 2384 8773 11179 4727 5824 7249 5499 11523 13906 15864 1925 11695 8020 841 437 5020 44 9923 10306 13199 17676 8583 4615 12916 14596 7595 17453 10861 7295 15734 5492 6129 15612 1628 14805 9899 9531 13180 14227 6951 13517 1136 8788 8593 11791 9535 13373 17634...
result:
ok OK
Test #11:
score: 0
Accepted
time: 4ms
memory: 15620kb
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 3633 2073 2710 727 413 2390 4268 142 3760 1791 2554 327 1560 1925 1222 336 3949 2260 3354 3138 2730 2623 2030 3490 3193 717 2356 1299 4063 1582 2518 2427 64 1287 2810 2577 1477 513 4098 3072 2148 900 1669 2927 1339 2138 2822 486 439 3051 771 4288 2899 452 2894 1199 2591 2868 4147 1550...
result:
ok OK
Test #12:
score: 0
Accepted
time: 34ms
memory: 17988kb
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 23349 7151 23339 12906 10969 21289 22943 24289 20851 10187 8227 24326 21981 7203 10661 15118 25255 8094 21051 22477 13956 23876 7113 9559 20455 22602 14675 8228 16076 18120 22455 3759 25043 5098 11611 16137 4020 25859 12710 17733 5752 16894 26237 23337 4046 13611 23893 13741 25923 ...
result:
ok OK
Test #13:
score: 0
Accepted
time: 80ms
memory: 19568kb
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 10061 799 14110 29442 20494 31404 26764 28991 24773 12616 16339 23468 22326 17303 32977 23324 10223 29873 3162 9601 21121 2957 7833 35166 23473 605 11304 11580 16358 12326 24171 24562 16554 11619 9211 12446 1638 293 4373 23195 14138 26524 3989 19657 17999 15299 19504 11510 18830 198...
result:
ok OK
Test #14:
score: 0
Accepted
time: 25ms
memory: 17304kb
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 12590 5579 1491 3061 10301 7257 8308 8224 6148 12835 3654 2596 12121 9937 745 7980 11395 11394 7444 8149 13177 2676 87 6347 6046 7367 8581 9079 14763 6075 8135 4195 8181 14096 4200 7696 6917 4689 2039 13171 11852 6487 6142 9979 3056 72 11959 3090 7936 7569 4810 12431 2101 14083 2226 1...
result:
ok OK
Test #15:
score: 0
Accepted
time: 2ms
memory: 16460kb
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 36 26 39 10 25 3 30 44 28 20 31 17 21 12 42 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: 1ms
memory: 16596kb
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...
result:
ok OK
Test #17:
score: 0
Accepted
time: 0ms
memory: 16108kb
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 35 59 10 46 75 62 71 56 55 1 9 38 11 77 29 87 50 30 15 64 4 24 76 23 21 2 70 80 52 79 48 26 39 83 41 22 63 19 85 14 6 49 73 33 40 66 8 86 44 58 84 67 25 69 36 27 57 61 5 37 28 43 81 60 20 72 78 3 65 7 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 ...
result:
ok OK
Test #18:
score: 0
Accepted
time: 2ms
memory: 15608kb
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 15 6 42 20 27 9 12 38 8 48 40 51 46 10 13 35 17 3 16 1 45 7 23 47 14 22 26 4 21 31 24 44 50 5 29 17 2 19 18 28 41 39 16 49 32 43 30 33 34 36 25 37 52
result:
ok OK
Test #19:
score: 0
Accepted
time: 2ms
memory: 16532kb
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 67 57 60 52 32 42 51 15 25 54 6 5 7 62 59 39 29 3 34 26 19 68 13 21 9 55 17 40 28 44 66 24 47 16 10 36 63 22 4 65 38 31 27 58 20 11 56 69 61 8 33 35 41 18 30 53 12 50 2 49 46 43 37 23 1 14 45
result:
ok OK
Test #20:
score: 0
Accepted
time: 3ms
memory: 15724kb
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 75 45 79 40 74 51 15 46 18 70 21 58 83 3 19 67 31 81 65 63 13 8 69 42 10 84 47 78 62 54 37 14 86 7 49 24 50 6 64 28 11 32 25 35 87 82 16 85 41 34 61 57 73 80 30 43 72 1 2 66 44 53 55 4 12 22 38 26 68 29 23 59 71 17 6 5 39 48 60 27 36 6 9 56 76 20 77 33
result:
ok OK