模板 - 强连通分量/割点/桥

int dfn[N], low[N], dfncnt, s[N], tp;

int scc[N], sc;  // 结点 i 所在 scc 的编号

int sz[N];       // 强连通 i 的大小

void tarjan(int u) {

    low[u] = dfn[u] = ++dfncnt, s[++tp] = u;

    for(int i = h[u]; i; i = e[i].nex) {

        const int &v = e[i].t;

        if(!dfn[v])

            tarjan(v), low[u] = min(low[u], low[v]);

        else if(!scc[v])

            low[u] = min(low[u], dfn[v]);

    }

    if(dfn[u] == low[u]) {

        ++sc;

        while(s[tp] != u)

            scc[s[tp]] = sc, sz[sc]++, --tp;

        scc[s[tp]] = sc, sz[sc]++, --tp;

    }

}

割点：

对于根节点，判断是不是割点很简单——计算其子树数量，如果有2棵即以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。

对于非根节点，判断是不是割点就有些麻烦了。我们维护两个数组dfn[]和low[]，dfn[u]表示顶点u第几个被（首次）访问，low[u]表示顶点u及其子树中的点，通过回边，能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）。对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点。

假设当前顶点为u，则默认low[u]=dfn[u]，即最早只能回溯到自身。

有一条边(u, v)，如果v未访问过，继续DFS，DFS完之后，low[u]=min(low[u], low[v])；

如果v访问过（且u不是v的父亲），就不需要继续DFS了，一定有dfn[v]<dfn[u]，low[u]=min(low[u], dfn[v])。

下面这个ufa的意思是uROOT，他就喜欢传个fa

void tarjan (int u,int fa)

{

    DFN[u]=LOW[u]=++idx;

    int child=0;

    for (int i=head[u];i!=0;i=pre[i].mark)

    {

        int nx=pre[i].nxt;

        if (!DFN[nx])

        {

            tarjan (nx,fa);

            LOW[u]=min (LOW[u],LOW[nx]);

            if (LOW[nx]>=DFN[u]&&u!=fa)

                cut[u]=1;

            if(u==fa)

                child++;

        }

        LOW[u]=min (LOW[u],DFN[nx]);

    }

    if (child>=2&&u==fa)

        cut[u]=1;

}

 for (int i=1;i<=n;i++)

        if (DFN[i]==0)

            tarjan (i,i);

    for (int i=1;i<=n;i++)

        if (cut[i])

            tot++;

割边：

和割点差不多，还叫做割桥。

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

实现

和割点差不多，只要改一处：low(v)>dfn(u)就可以了，而且不需要考虑根节点的问题。

割边是和是不是根节点没关系的，原来我们求割点的时候是指点v是不可能不经过父节点u为回到祖先节点（包括父节点），所以顶点u是割点。如果low(v)==dfn(u)表示还可以回到父节点，如果顶点v不能回到祖先也没有另外一条回到父亲的路，那么(u,v)这条边就是割边。

巴特西

模板 - 强连通分量/割点/桥 - Tarjan

最新文章

热门文章