救救孩子吧,ACon2,6,8,10

P3387 【模板】缩点

@[amxxxxx](/user/534430) `tarjan` 写错了,我也遇到过差不多的问题。[link](https://www.luogu.com.cn/discuss/515584)。
by char_cha_ch @ 2022-12-21 20:21:56


@[kirihara233](/user/701221) 怎么错的啊,没感觉顺序有问题啊,我是直接原数组上面加权值的
by amxxxxx @ 2022-12-23 14:09:03


@[amxxxxx](/user/534430) 好像没错,再看了一下。 我最近眼睛有点瞎![](//图.tk/1)。
by char_cha_ch @ 2022-12-23 14:12:31


@[amxxxxx](/user/534430) tarjan 和 拓扑排序都有些错误,其中拓扑排序可以看看统计答案部分
by CodeBoy @ 2022-12-23 15:50:47


@[amxxxxx](/user/534430) 修改后的Tarjan部分如下: ```cpp void tarjan(int k) { s[++top]=k; vis[k]=1; dfn[k]=++ti,low[k]=ti; for (int i=head[k];i;i=edge[i].nxt) { int v=edge[i].v; if (!dfn[v]) { tarjan(v); low[k]=min(low[k],low[v]); } else if (vis[v]) { low[k]=min(low[k],low[v]); } } if (dfn[k]==low[k]) { int x; while (x=s[top--]) { sec[x]=k; vis[x]=0; if (k==x) break; a[k]+=a[x]; } } } ```
by CodeBoy @ 2022-12-23 15:59:37


@[CodeBoy](/user/253068) 都看见了,我是啥b()统计答案数组用a,更新low用时间戳
by amxxxxx @ 2022-12-23 16:00:51


@[amxxxxx](/user/534430) 答案直接累加都能水过 40pt 也是难蚌。
by CodeBoy @ 2022-12-23 16:21:19


|