割点和割边

在无向图中，所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的点，如果删除它，会把这个连通分量分成两个或更多，这种点称为割点（cut vertex）。
在一个连通分量中，如果删除一条边，把这个连通分量分成两个，这个边称为割边（cut eddge，又称为桥，bridge）。

深搜优先生成树

1. T 的根节点 s 是割点，当且仅当 s 有两个或更多的子结点。
2. T 的非根节点 u 是割点，当且仅当 u 存在一个子结点 v，v 及其后代都没有回退边连回 u 的祖先。
   

// 割点
vector<int> g[maxn];
int dfn[maxn], low[maxn], cnt;   // 遍历顺序、祖先
int vis[maxn], num;              // 标记割点

void dfs(int x, int fa, int son = 0) {
    dfn[x] = low[x] = ++ cnt;
    for(auto to: g[x]) {
        if (!dfn[to]) {
            dfs(to, x);
            low[x] = min(low[to], low[x]);
            if (x == fa) vis[x] = ++son > 1 ? 1 : 0;  // 判断根结点是否为割点
            else if (low[to] >= dfn[x]) vis[x] = 1;   // 判断非根结点是否为割点
            // 判断割边，把low[to] >= dfn[x] 改为 low[to] > dfn[x] 即可
        }
        else if (to != fa) {
            low[x] = min(dfn[to], low[x]);
        }
    }
    if (vis[x]) num ++;  // 统计割点个数
}

void tarjin(int n) { // 无向连通图求割点
    cnt = num = 0;
    for(int i = 1; i <= n; ++ i) {
        dfn[i] = low[i] = vis[i] = 0;
    }
    for(int i = 1; i <= n; ++ i) {
        if (!dfn[i]) dfs(i, i);
    }
    for(int i = 1; i <= n; ++ i) g[i].clear();
}

// 割边
vector<int> g[maxn];
int dfn[maxn], low[maxn], cnt;
vector<pair<int,int> > bridge;   // 存储割边

void dfs(int x, int fa, int k = 0) {
    dfn[x] = low[x] = ++cnt;
    for(auto to: g[x]) {
        if (to == fa && ++k == 1) continue; // 判重边
        if (!dfn[to]) {
            dfs(to, x);
            low[x] = min(low[to], low[x]);
            if (low[to] > dfn[x]) { 
                bridge.push_back(make_pair(min(x,to), max(x,to)));  // 存储割边
            }
        }
        else low[x] = min(dfn[to], low[x]);
    }
}

void tarjin(int n) {
    cnt = 0; L.clear();
    for(int i = 1; i <= n; ++ i) {
        dfn[i] = low[i] = 0;
    }
    for(int i = 1; i <= n; ++ i) {
        if (!dfn[i]) dfs(i, i);
    }
    for(int i = 1; i <= n; ++ i) g[i].clear();
}

双连通分量

在一个连通图中选任意两点，如果它们之间至少存在两条“点不重复”的路径，称为点双连通。一个图中的点双连通极大子图称为“点双连通分量”（block，或者 2-connected component）。点双连通分量是一个“可靠”的图，去掉任何一个点，其他点仍然是连通的。也就是说，点双连通分量中没有割点。
类似地有“边双连通分量”，如果任意两点之间至少存在两条“边不重复”的路径，称为“边双连通”。在边双连通图中去掉任意一条边，图任然是连通的。也就是说，边双连通图中没有割边。

边双连通分量

vector<int> g[maxn];
int dfn[maxn], low[maxn], cnt;
int bcc[maxn], tot;  // 边双连通分量
int sta[maxn], top;
int bridge[maxn], pre[maxn];  // 标记割边
int du[maxn];    // 缩点度数

void dfs(int x, int fa, int k = 0) {
    dfn[x] = low[x] = ++cnt;
    sta[top++] = x;
    for(int i = 0; i < g[x].size(); ++ i) {
        int to = g[x][i];
        if (to == fa && ++k == 1) continue; // 判重边
        if (!dfn[to]) {
            dfs(to, x);
            low[x] = min(low[to], low[x]);
            pre[to] = x;   // 标记父节点
            if (low[to] > dfn[x]) bridge[to] = 1;  // 标记割边
        }
        else low[x] = min(dfn[to], low[x]);
    }
    if (dfn[x] == low[x]) {  // 弹出一个边连通分量
        tot ++;
        while(1) {
            int y = sta[--top];
            bcc[y] = tot;
            if (x == y) break;
        }
    }
}

void tarjin(int n) {
    top = cnt = tot = 0;
    for(int i = 1; i <= n; ++ i) {
        bcc[i] = dfn[i] = low[i] = 0;
    }
    for(int i = 1; i <= n; ++ i) {
        if (!dfn[i]) dfs(i, i);
    }

    for(int i = 1; i <= n; ++ i) { // 统计缩点度数
        if (bridge[i]) {
            du[bcc[i]] ++;
            du[bcc[pre[i]] ++;
        }
    }
    int leaf = 0; 
    for(int i = 1; i <= tot; ++ i) { // 统计缩点后的叶子结点
        if (du[i] == 1) leaf ++;
    }

    for(int i = 1; i <= n; ++ i) {
        g[i].clear();
    }
}