【模板】Tarjan

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\) 的时间戳。由于它是一个图，所以会有一些边返回到其它访问过的点（有可能是它的兄弟或者祖先，这不重要），称作返祖边。

记录 \(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 无向图割点

原文地址：http://www.cnblogs.com/caijianhong/p/16863431.html