缩点重构图时,这样是龊的。
for(int u=1;u<=n;++u){
++siz[col[u]];
for(int i=g1.head[u];i;i=g1.nxt[i]){
int v=g1.to[i];
if(col[u]!=col[v])
g2.add(col[u],col[v]),g2.add(col[v],col[u]);
else ++Siz[col[u]];
}
}
因为 u→v,v→u 一共会建 4 条边。
这样就对了。
for(int u=1;u<=n;++u){
++siz[col[u]];
for(int i=g1.head[u];i;i=g1.nxt[i]){
int v=g1.to[i];
if(col[u]!=col[v])
g2.add(col[u],col[v]);
else ++Siz[col[u]];
}
}