关于缩点建新边时去重
  • 板块学术版
  • 楼主Gyc_Fisher
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/11/6 19:16
  • 上次更新2023/11/7 13:31:25
查看原帖
关于缩点建新边时去重
978312
Gyc_Fisher楼主2023/11/6 19:16

本蒟蒻看到一份题解,发现他的缩点后建新边去重是这样写的:

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;//删除标记
	}
}

这么写是不是有些许的问题,比如下图的情况: 按上述代码在 11 和 22 组成的强连通分量中,在访问 11 和 22 的时候都会使得这个强连通分量向 33 这个点建边,不就没有起到去重的作用吗?(雾)

2023/11/6 19:16
加载中...