割点和点双连通分量

#include <bits/stdc++.h>
using namespace std;

const int N = 20005;
vector<int> g[N];
int dfn[N], low[N], tot;
bool cut[N];

void tarjan(int u, bool root) {
    dfn[u] = low[u] = ++tot;
    int son = 0;
    for (int v : g[u]) {
        if (!dfn[v]) {
            son++;
            tarjan(v, false);
            low[u] = min(low[u], low[v]); 
            if (low[v] >= dfn[u] && (!root || son >= 2)) cut[u] = true;
        } else {
            low[u] = min(low[u], dfn[v]); // 弃边 dfn[v] > dfn[u] 不影响最小值
        }
    } 
}