QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340631#996. 割点FISHER_#WA 3ms5620kbC++14750b2024-02-29 10:51:482024-02-29 10:51:49

Judging History

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

  • [2024-02-29 10:51:49]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5620kb
  • [2024-02-29 10:51:48]
  • 提交

answer

#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
using namespace std;
const int maxn = 20000;
vector<int> g[maxn + 5];
vector<int> out;
int dfn[maxn + 5], low[maxn + 5], stamp;
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++stamp;
	for (int v : g[u]) 
		if (v != fa) {
			if (!dfn[v]) {
				tarjan(v, u);
				low[u] = min(low[u], low[v]);
			} else low[u] = min(low[u], dfn[v]);
		}
	if (low[u] == dfn[u]) out.PB(u); 
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].PB(v), g[v].PB(u);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i, 0);
	sort(out.begin(), out.end());
	for (int x : out) printf("%d\n", x);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 5620kb

input:

12783 21968
4933 7832
8238 2739
3628 7841
9169 6390
7850 8797
8120 8710
5306 9807
10166 2063
2666 5157
5015 4651
4790 12586
10366 7137
12440 7218
6330 3670
2735 8492
1968 2750
6237 1112
6578 9221
743 3820
7155 4583
2537 9747
11331 9916
4454 5631
2978 10340
5293 1803
4944 4296
11800 2742
7903 2018
10...

output:

1
9
14
23
24
27
28
29
30
33
36
38
39
56
82
93
109
111
112
116
119
120
123
124
129
131
136
142
147
151
154
155
160
166
175
181
183
185
197
201
207
239
265
270
289
293
295
302
313
316
318
319
328
336
347
358
371
373
378
383
387
389
393
400
419
424
440
451
453
471
485
489
494
500
502
511
520
526
530
53...

result:

wrong answer 1st numbers differ - expected: '1440', found: '1'