警示后人
查看原帖
警示后人
815796
zzy0618楼主2024/11/13 22:55

缩点重构图时,这样是龊的。

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]];
        }
    }

因为 uv,vuu\to v,v\to u 一共会建 44 条边。

这样就对了。

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]];
        }
    }
2024/11/13 22:55
加载中...