2018-team4-modules-割点

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//若cut[u]=1则u为割点 
void Tarjan(int u) {
    dfn[u] = low[u] = ++tme;
    for (int i=0;i<(int)e[u].size();i++) {
        int v = e[u][i];
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
            if (low[v] >= dfn[u]) {
                if (u == now) deg++; else cut[u] = 1; 
            }
        } else
            low[u] = min(low[u],dfn[v]);
    }
    return ;
}
}}}

//若cut[u]=1则u为割点 
void Tarjan(int u) {
    dfn[u] = low[u] = ++tme;
    for (int i=0;i<(int)e[u].size();i++) {
        int v = e[u][i];
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
            if (low[v] >= dfn[u]) {
                if (u == now) deg++; else cut[u] = 1; 
            }
        } else
            low[u] = min(low[u],dfn[v]);
    }
    return ;
}