本蒟蒻看到一份题解,发现他的缩点后建新边去重是这样写的:
for(int i=1;i<=n;i++){
for(int j=h[i];j;j=e[j].nxt){
if(col[i]==col[e[j].v]||vv[col[e[j].v]])continue;
addedge(col[i],col[e[j].v]);
vv[col[e[j].v]]=true;
}
for(int j=h[i];j;j=e[j].nxt)vv[col[e[j].v]]=false;
}
}
这么写是不是有些许的问题,比如下图的情况:
按上述代码在 1 和 2 组成的强连通分量中,在访问 1 和 2 的时候都会使得这个强连通分量向 3 这个点建边,不就没有起到去重的作用吗?(雾)