QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671044 | #906. 强连通分量 | dieselhuang | WA | 155ms | 45384kb | C++14 | 1.1kb | 2024-10-24 10:24:05 | 2024-10-24 10:24:05 |
Judging History
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;
}
詳細信息
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)