QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671044#906. 强连通分量dieselhuangWA 155ms45384kbC++141.1kb2024-10-24 10:24:052024-10-24 10:24:05

Judging History

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

  • [2024-10-24 10:24:05]
  • 评测
  • 测评结果:WA
  • 用时:155ms
  • 内存:45384kb
  • [2024-10-24 10:24:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, dfx = 0, tp = 0, sct = 0, hd[500010], e[500010][2], dfn[500010], low[500010], scc[500010], st[500010];
bool bk[500010];
vector<int> ans[500010];
void dfs(int u){
	int i, v, tmp = tp;
	dfn[u] = ++dfx; low[u] = dfn[u]; st[++tp] = u; bk[u] = true;
	for(i = hd[u]; i > 0; i = e[i][0]){
		v = e[i][1];
		if(dfn[v] == 0){
			dfs(v);
			low[u] = min(low[u], low[v]);
		}else if(bk[v]) low[u] = min(low[u], dfn[v]);
	}
	bk[u] = false;
	if(low[u] >= dfn[u]){
		sct++;
		while(tp > tmp){
			v = st[tp--];
			scc[v] = sct; ans[sct].push_back(v);
		}
	}
}
int main()
{
	int i, j, u, v;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++) hd[i] = 0, dfn[i] = 0, bk[i] = false;
	for(i = 1; i <= m; i++){
		scanf("%d%d", &u, &v); u++; v++;
		e[i][0] = hd[u]; e[i][1] = v; hd[u] = i;
	}
	for(i = 1; i <= n; i++){
		if(dfn[i] == 0) dfs(i);
	}
	printf("%d\n", sct);
	for(i = sct; i > 0; i--){
		printf("%d ", ans[i].size());
		for(j = 0; j < ans[i].size(); j++) printf("%d ", ans[i][j] - 1);
		printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 26196kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
1 5 
2 4 1 
1 2 
2 3 0 

result:

ok OK

Test #2:

score: -100
Wrong Answer
time: 155ms
memory: 45384kb

input:

500000 500000
389812 410922
255712 339244
274009 248522
347288 199231
235313 301629
469588 84917
364188 449407
392348 436920
26220 198288
162188 468965
274222 92196
463222 408478
231663 467768
382681 38083
412497 160479
280851 268689
101149 25450
62271 9177
38892 268598
273853 250782
191939 89247
40...

output:

499600
1 499999 
1 499995 
1 499994 
1 499989 
1 499988 
1 499987 
1 499983 
1 499978 
1 499975 
1 499972 
1 499969 
1 499965 
1 499964 
1 499954 
1 499949 
1 499947 
1 499942 
1 499939 
1 499932 
1 499928 
1 499926 
1 499925 
1 499924 
1 499919 
1 499918 
1 499915 
1 499910 
1 499909 
1 499907 
1 4...

result:

wrong answer 275774 is later than 246508, but there is an edge (275774, 246508)