缩点后加边如果加双向边,#5 #6 两个测试点会超时。
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=e[j].next)
if(col[e[j].v]!=col[i])
{
addedge2(col[e[j].v],col[i]);
addedge2(col[i],col[e[j].v]);
}
而加单向边就不会有这样的问题。
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=e[j].next)
if(col[e[j].v]!=col[i])
addedge2(col[i],col[e[j].v]);
所以是为啥啊