QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92956#999. 边双连通分量Appleblue17#AC ✓225ms44788kbC++141.1kb2023-03-31 09:15:402023-03-31 09:15:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-31 09:15:44]
  • 评测
  • 测评结果:AC
  • 用时:225ms
  • 内存:44788kb
  • [2023-03-31 09:15:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
vector < pair<int,int> > G[N];

int dfn[N],low[N],id;
bool vis[N],cut[N];
void tarjan(int u,int fa){
	dfn[u]=low[u]=++id;
	vis[u]=1;
	for(pair<int,int> e: G[u]){
		int v=e.first,num=e.second;
		if(num==fa) continue;
		if(!dfn[v]){
			tarjan(v,num);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]) cut[num]=1;
		}
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
}

int aid;
vector <int> ANS[N];
void dfs(int u){
	if(vis[u]) return ;
	vis[u]=1;
	ANS[aid].push_back(u);
	for(pair<int,int> e: G[u]){
		int v=e.first,num=e.second;
		if(cut[num]) continue;
		dfs(v);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v; cin>>u>>v; u++,v++;
		G[u].push_back({v,i});
		G[v].push_back({u,i});
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,0);
	
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		aid++;
		dfs(i);
	}
	cout<<aid<<'\n';
	for(int i=1;i<=aid;i++){
		cout<<ANS[i].size()<<" ";
		for(int x: ANS[i]) cout<<x-1<<" ";
		cout<<'\n';
	}
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 29860kb

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: 29728kb

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: 3ms
memory: 27992kb

input:

2 2
0 1
1 0

output:

1
2 0 1 

result:

ok OK

Test #4:

score: 0
Accepted
time: 225ms
memory: 43864kb

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: 176ms
memory: 44788kb

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: 152ms
memory: 44676kb

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: 90ms
memory: 40272kb

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: 91ms
memory: 39784kb

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: 53ms
memory: 34856kb

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: 25ms
memory: 32392kb

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: 3ms
memory: 28580kb

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: 32ms
memory: 31524kb

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: 52ms
memory: 34452kb

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: 31ms
memory: 32024kb

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: 1ms
memory: 29672kb

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: 2ms
memory: 29860kb

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: 3ms
memory: 29712kb

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: 1ms
memory: 29872kb

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 24 44 50 5 29 31 
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: 1ms
memory: 29824kb

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: 1ms
memory: 29752kb

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 36 27 60 
6 9 56 76 33 20 77 

result:

ok OK