桥

定义：删除这条边后连通块数量加1

思考先暴力搜出一棵树，然后对于每一条非树边都会构成一个环，这个环上的边就不可能是桥了（拿样例来看）

\(1 \rightarrow 2\) 和 \(5 \rightarrow 6\) 就是桥
假如用 \(lca\) 来维护加一个树上差分码量就有点惊人了
考虑优化
如果搜树的顺序改为 \(dfs\) 序，那么非树边就一定是父亲指向儿子，那么就不需要 \(lca\) 了
还有一种做法叫 \(tarjan\)
记 \(low_u\) 为 \(dfs\) 树上子树 \(u\) 内所有节点中，仅通过非树边能够抵达的结点之中 \(dfs\) 序最小者
那么如果是树边 \(low_u = min(low_u, low_v)\)，如果不是树边 \(low_u = min(low_u, dfn_v)\)
code:

void dfs(int u, int f) {
  dfn[u] = low[u] = ++dcnt;
  for (auto e : g[u]) {
    if (e.id == f) {
      continue;
    }
    int v = e.v, id = e.id;
    if (!dfn[v]) {
      dfs(v, id);
      low[u] = min(low[u], low[v]);
    }
    else low[u] = min(low[u], dfn[v]);
  }
  if (f != 0 && dfn[u] == low[u]) {
    ans.push_back(ans);
  }
}

割点

定义：删除这个点后连通块数量加1

首先和桥一样的找环做法就 \(pass\) 掉了，数据：

3为割点
方法：
我们对于 \(u\) 的所有树上结点遍历一遍
如果有某个 \(low_v >= dfn_u\) 说明如果 \(u\) 没了，那么 \(v\) 就会单独成为一个连通块，\(u\) 就是割点
注意事项：
1.叶子节点永远不是
2.根节点要判树边的数量是否 \(>1\)
code:

void dfs(int u, int f) {
  dfn[u] = low[u] = ++dcnt;
  for (auto e : g[u]) {
    if (e.id == f) {
      continue;
    }
    int v = e.v, id = e.id;
    if (!dfn[v]) {
      dfs(v, id);
      low[u] = min(low[u], low[v]);
      cnt[u]++;
      if (cnt[u] > 1 && f == 0) {
        vis[u] = true;
      }
      if (low[e.v] >= dfn[u] && f != 0) {
        vis[u] = true;
      }
    }
    else low[u] = min(low[u], dfn[v]);
  }
}

边双连通分量

直接删去没条桥，搜连通块