C++ – 割点

使用 Tarjan 算法

lli fa[maxn];
lli dfn[maxn];
lli low[maxn];
bool cut[maxn];

void tarjan(lli u) {
    dfn[u] = ++cnt;
    low[u] = dfn[u];
    lli child = 0;
    for (lli i = 0; i < mp[u].size(); ++i) {
        lli v = mp[u][i];
        if (!dfn[v]) {
            ++child;
            fa[v] = u;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (fa[u] != 0 && low[v] >= dfn[u])
                cut[u] = true;
        }
        else if (fa[u] != v && fa[u] != 0) 
            low[u] = min(low[u], dfn[v]);
    }
    if (fa[u] == 0 && child >= 2)
        cut[u] = true;
}