QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791959 | #999. 边双连通分量 | _FJqwq | AC ✓ | 103ms | 31748kb | C++23 | 1.0kb | 2024-11-28 22:28:27 | 2024-11-28 22:28:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+5;
int n,m,dfn[N],low[N],tot1,tot2,col[N],cut[N];
struct edge{int to,id;};
vector<edge>v[N];
vector<int>g[N];
void dfs1(int x,int i){
dfn[x]=low[x]=++tot1;
for(edge e:v[x]){
if(e.id==i) continue;
if(!dfn[e.to]){
dfs1(e.to,e.id);
low[x]=min(low[x],low[e.to]);
if(low[e.to]>=dfn[x]) cut[e.id]=1;
}
else{
low[x]=min(low[x],dfn[e.to]);
}
}
}
void dfs2(int x){
if(col[x]) return ;
col[x]=tot2;
g[tot2].push_back(x);
for(edge e:v[x])
if(!cut[e.id]) dfs2(e.to);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
x++,y++;
v[x].push_back(edge{y,i});
v[y].push_back(edge{x,i});
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs1(i,0);
for(int i=1;i<=n;i++) if(!col[i]){
tot2++;
dfs2(i);
}
printf("%d\n",tot2);
for(int i=1;i<=tot2;i++){
printf("%d ",g[i].size());
for(int e:g[i]) printf("%d ",e-1);
puts("");
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 6004kb
input:
4 5 0 2 0 1 3 0 2 1 2 3
output:
1 4 0 1 2 3
result:
ok OK
Test #2:
score: 0
Accepted
time: 4ms
memory: 5968kb
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 1 9 4 2 12 3 10 3 6 7 8
result:
ok OK
Test #3:
score: 0
Accepted
time: 4ms
memory: 6028kb
input:
2 2 0 1 1 0
output:
1 2 0 1
result:
ok OK
Test #4:
score: 0
Accepted
time: 95ms
memory: 31640kb
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 34003 173979 98603 31275 149837 133486 130383 118720 50292 71542 152711 35343 61341 122597 183977 146613 93152 97912 145190 136692 188152 138949 17720 78182 18806 154070 156250 52253 135099 126612 146991 67489 12...
result:
ok OK
Test #5:
score: 0
Accepted
time: 103ms
memory: 29708kb
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 82146 4627 9684 86726 86806 35034 137640 185421 44210 154684 83460 141690 89393 30121 57914 109046 94674 61684 106340 185606 107745 118516 154575 58987 17022 35439 121189 193964 91482 11337 82797 7647 115692 78298 143818 71124 9271 163117 156126 185304 17438 36202 94365 49852 90591 64...
result:
ok OK
Test #6:
score: 0
Accepted
time: 91ms
memory: 31748kb
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 4357 123762 156908 47125 21862 3374 10608 144194 180986 127061 30267 35926 197388 4931 193917 129271 55709 44519 74001 129805 163527 50018 46942 145467 112370 76943 161538 112969 78228 25261 101351 189578 83128 88754 47063 40114 116119 160008 65006 29845 25755 166020 38857 150641 1292...
result:
ok OK
Test #7:
score: 0
Accepted
time: 58ms
memory: 21504kb
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 46862 85531 9042 75706 73830 119869 4258 20592 50824 109635 94204 26573 14238 36889 104084 101586 113081 8190 100296 124984 114072 82557 18575 27048 82980 73595 90213 105910 76335 12199 55467 77576 112654 66733 126361 6583 67712 20345 35726 56308 62743 91537 36522 13...
result:
ok OK
Test #8:
score: 0
Accepted
time: 67ms
memory: 23808kb
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 88101 25401 76580 44372 124874 112034 95496 111532 101440 84553 84003 95843 15975 16016 73709 97018 115586 110472 36431 2533 108748 86871 30274 141165 124105 54268 27892 132326 34767 100303 77799 107918 88148 81938 49466 74362 25981 111858 22509 65418 13740 144117 85988 67939 92766 135...
result:
ok OK
Test #9:
score: 0
Accepted
time: 40ms
memory: 14268kb
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 32623 12826 540 43534 15796 12328 1394 24591 497 24206 51087 17347 26087 26787 36315 45814 4730 47880 50346 8140 50724 9613 1288 3781 24593 43938 4608 47269 6495 499 48583 31956 30507 3117 25370 5187 8965 4069 24940 8207 40011 34544 2950 10388 24791 6360 9927 26084 23430 32556 18220 682...
result:
ok OK
Test #10:
score: 0
Accepted
time: 23ms
memory: 9216kb
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 6372 16303 4303 6828 11430 14094 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 15543 8841 786 16072 11179 4727 5824 7249...
result:
ok OK
Test #11:
score: 0
Accepted
time: 8ms
memory: 6784kb
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 3240 4147 2868 1137 798 2863 2002 757 1015 2356 1299 4063 1582 2518 2427 2554 327 1560 1925 1222 336 2390 413 4268 142 3760 1791 18 3337 2852 789 1690 2829 442 2130 1280 3799 3702 341 2791 3130 1567 730 2730 3138 536 2632 2404 2837 1643 2228 365 2569 4191 1335 330 1189 3424 439 486 1705 39...
result:
ok OK
Test #12:
score: 0
Accepted
time: 29ms
memory: 10496kb
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 3993 18120 16076 8228 14574 21527 13825 149 9886 18230 1781 10953 6333 7347 19223 24813 13552 4383 9504 9431 25149 9256 3032 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 1842 3367 22717 23...
result:
ok OK
Test #13:
score: 0
Accepted
time: 38ms
memory: 13940kb
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 33260 34548 15856 3361 33491 15299 17999 19657 3989 26524 14138 23195 6281 4653 11617 2571 28664 10223 23324 1899 22712 28729 32399 31515 24885 29873 3162 9601 21121 2957 7833 35166 23473 605 11304 11580 16358 12326 24171 24562 16554 11619 9211 12446 1638 293 4373 8799 35128 22422 21846 4...
result:
ok OK
Test #14:
score: 0
Accepted
time: 15ms
memory: 8508kb
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 458 3853 13110 9361 14543 13549 9578 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 10301 3061 1491 5579 12590 4278 6347 87 2676 13177 8149 7444 11394 12714 13088 775 6085 1406 1862 5315 4486 4148 14702 ...
result:
ok OK
Test #15:
score: 0
Accepted
time: 4ms
memory: 5968kb
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 25 10 39 26 36 46 42 12 21 31 17 28 20 44 30 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: 4ms
memory: 5972kb
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: 4ms
memory: 5924kb
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 86 44 58 80 52 79 48 26 70 2 62 71 56 55 1 9 38 11 77 29 87 50 30 15 64 4 75 46 10 59 35 17 83 39 41 23 76 24 65 32 21 33 73 49 40 66 8 6 60 81 43 28 57 25 69 36 27 61 5 37 20 72 22 63 19 85 14 7 67 84 3 78 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: 4ms
memory: 5856kb
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 6 42 20 27 9 12 38 8 48 40 51 46 10 13 35 17 11 15 3 16 1 45 7 23 47 14 22 26 4 31 24 44 50 5 21 29 17 2 43 30 28 18 19 52 16 39 41 49 32 25 37 34 33 36
result:
ok OK
Test #19:
score: 0
Accepted
time: 5ms
memory: 6036kb
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 64 48 43 37 23 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 67 57 14 45 46 49 1 11 56 69 61 8 33 35 41 18 30 53 12 50 2
result:
ok OK
Test #20:
score: 0
Accepted
time: 4ms
memory: 6052kb
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 11 49 7 6 64 28 86 14 37 54 62 84 47 78 10 69 42 65 63 31 81 67 19 25 35 87 32 21 70 18 3 58 83 15 46 40 74 79 45 52 75 17 51 29 68 26 38 22 12 4 55 59 66 44 53 71 23 73 82 61 41 34 16 85 57 80 30 43 72 1 2 13 8 50 24 6 5 39 48 36 27 60 6 9 56 76 33 20 77
result:
ok OK