posted on 2022-07-07 20:52:49 | under 模板 | source
0x00 有向图缩点
现有一有向图 \(G=(V,E)\)，称一个点集 \(E'\in E\) 为强连通分量，当且仅当 \(E'\) 的任意两点可以互相到达（围成一个环），求出所有极大强连通分量即 \(\tt SCC\)。
使用 Tarjan，我们将这个有向图看成一棵树，dfs 遍历，用 \(dfn_u\) 记录访问点 \(u\) 的时间戳。由于它是一个图，所以会有一些边返回到其它访问过的点（一定是祖先，这是 dfs 生成树的性质），称作返祖边。
记录 \(low_u\)，它表示点 \(u\) 通过 dfs 树和最多一次返祖边能到达的最小的 \(dfn\)。如果 \(low_u=dfn_u\)，我们断言点 \(u\) 的整一棵子树是一个 \(SCC\)，因为从点 \(u\) 出发能回到点 \(u\)，就是一个环。但是，\(low_u\) 不能经过已经缩完点的点，这样两个 \(SCC\) 就套在一起了，可以合成一个大的 \(SCC\) 了。
点击查看代码
int dfn[1010],low[1010],stk[1010],col[1010],cnt,top,tot;
void reset(){
cnt=0;
tot=0;
memset(dfn,0,sizeof dfn);
memset(col,0,sizeof col);
}
void tarjan(int u){
low[stk[++top]=u]=dfn[u]=++cnt;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(!col[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
col[u]=++tot;
while(stk[top]!=u) col[stk[top--]]=tot;
top--;
}
}
0x01 边双连通分量
在缩点的基础上，强制不让它走到父亲边即可。
点击查看代码
graph<500010,2000010> g;
int dfn[500010],low[500010],stk[500010],cnt,top,col[500010],dcc,siz[500010];
bool vis[2000010<<1];
void tarjan(int u){
dfn[u]=low[stk[++top]=u]=++cnt;
for(int i=g.head[u];i;i=g.nxt[i]){
if(vis[i]||vis[i^1]) continue;
int v=g[i].v;
if(!dfn[v]) vis[i]=vis[i^1]=1,tarjan(v),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
col[u]=++dcc;
do col[stk[top]]=dcc; while(stk[top--]!=u);
}
}
0x02 无向图割点
与有向图缩点没有区别，在代码上。
但是，无向图割点的条件变为：\(low_v\geq dfn_u\)，这样 \(v\) 这个儿子就走不到 \(u\)，割掉 \(u\)，\(v\) 就过不来了。
点击查看代码
int dfn[500010],low[500010],stk[500010],cnt,top,cut[500010];
void tarjan(int u){
dfn[u]=low[stk[++top]=u]=++cnt,cut[u]=1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(!dfn[v]){
tarjan(v),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) cut[u]++;
}else low[u]=min(low[u],dfn[v]);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i),cut[i]--;
int ans=0;
for(int i=1;i<=n;i++) ans+=cut[i]>=2;
//cut[i] 表示割掉 i 点会剩下多少个连通块，割点就是 cut[i]>=2