桥：如果删除某条边图不联通，称该边为桥。
割点：如果删除某点及其附属边后整个图不连通，成该点为割点。
两类双连通分量
边双连通分量(e_DCC)：极大的不含桥的连通块。
删除边双连通分量中的任意边，整个图还是连通的
边双连通分量任意两点之间必有不少于两条不同路径
点双连通分量(v_DCC)/连通块：极大的不包含割点的连通块。
每一个割点至少属于两个点连通分量。

两个割点之间的边不一定是桥。例如一个H上边封闭的图。 桥两边的端点也不一定是割点。例如一条线段。

点连通分量和双连通分量也无必然关系 例如，一个8表示的图是边连通分量，不是点连通分量 一条线表示的图不是边连通分量，是点连通分量

对于一棵树来讲，每个节点都是一个边连通分量，每条边都是一个点连通分量

边连通分量

类似于强连通分量dfn, low数组
只存在前向边，树枝边，后向边，不存在横向边(因为边是没有方向的)

如何找到所有桥？
桥等价于对于一条树枝边x-y，dfn[x] < low[y]
如何找到所有边双连通分量？
方法1：删掉所有桥
方法2：类似于双连通分量的操作，使用栈辅助操作

AcWing 395. 冗余路径
边双连通分量等价于图上任意两点之间至少有两条完全不同的路径
证明：
充分性：反证法，假设图不是一个边双连通分量，说明存在桥，删除桥后，两侧节点之间没有可达路径，与已知矛盾，得证
必要性：归纳法
无向连通图，至少加多少条边能变成边双连通分量？
缩点后度为1的节点数(c + 1) // 2
连线方式：两个叶节点连起来与根节点成环。

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 5010, M = 20010;
  5.     static int[] h = new int[N], e = new int[M], ne = new int[M];
  6.     static int idx, p;
  7.     static int[] dfn = new int[N], low = new int[N], stk = new int[N];
  8.     static int dcc_cnt, time_cnt;
  9.     static int n, m;
  10.     static int[] id = new int[N];
  11.     static boolean[] is_bridge = new boolean[M];
  12.     static int[] degree = new int[N];
  13.     public static void main(String[] args) {
  14.         Scanner sc = new Scanner(System.in);
  16.         n = sc.nextInt();
  17.         m = sc.nextInt();
  19.         Arrays.fill(h, -1);
  20.         for (int i = 0; i < m; i++) {
  21.              int a = sc.nextInt();
  22.              int b = sc.nextInt();
  23.              add(a, b);
  24.              add(b, a);
  25.         }
  26.         tarjan(1, -1);
  27.         for (int i = 0; i < idx; i++) {
  28.             if (is_bridge[i]) {
  29.                 degree[id[e[i]]]++;
  30.             }
  31.         }
  33.         int c = 0;
  34.         for (int i = 1; i <= dcc_cnt; i++)
  35.             if (degree[i] == 1)
  36.                 c++;
  38.         System.out.println((c + 1) / 2);
  40.     }
  42.     static void tarjan(int u, int from) {
  43.         dfn[u] = low[u] = ++time_cnt;
  44.         stk[++p] = u;
  46.         for (int i = h[u]; i != -1; i = ne[i]) {
  47.             int j = e[i];
  48.             if (dfn[j] == 0) {
  49.                 tarjan(j, i);
  50.                 low[u] = Math.min(low[u], low[j]);
  51.                 if (dfn[u] < low[j]) {
  52.                     is_bridge[i] = is_bridge[i ^ 1] = true;
  53.                 }
  54.             } else if ((i ^ 1) != from) {
  55.                 low[u] = Math.min(low[u], dfn[j]);
  56.             }
  57.         }
  59.         if (dfn[u] == low[u]) {
  60.             int y;
  61.             dcc_cnt++;
  62.             do {
  63.                 y = stk[p--];
  64.                 id[y] = dcc_cnt;
  65.             } while (y != u);
  66.         }
  67.     }
  69.     static void add(int a, int b) {
  70.         e[idx] = b;
  71.         ne[idx] = h[a];
  72.         h[a] = idx++;
  73.     }
  74. }

点双连通分量

类似于强连通分量dfn, low数组

如何判断一个点是不是割点？
对于一条树枝边x-y，若low[y] >= dfn[x]

  • 如果x不是根节点，那么x是割点
  • x是根节点，至少有两个子节点yi，满足low[yi] >= dfn[x]

AcWing 1183. 电力
求每个割点最多能将图分成几个连通块

如何求点双连通分量？

  1. // 求完tarjan(j)后
  2. if (dfn[u] <= low[j]) {
  3.      cnt++;
  4.     if (u != root || cnt > 1) // 说明x是割点
  5.     {
  6.          // 记录该点为割点
  7.     }
  9.     // 将栈中元素弹出，直至j被弹出为止
  10.     // 将u加入该点双连通分量中
  11. }
  13. // 最后判断u是不是孤立点

AcWing 396. 矿场搭建
分别处理每个连通块
若连通块内无割点，任选两个点作为两个出口即可，cnt * (cnt - 1) / 2
若连通块内有割点，先缩点

  • 每个割点作为单独一个点
  • 从每个v-DCC向其所包含的每个割点连一条边，这样缩点后的图最多有2倍的原点数量
    • v-DCC度为1（相当于叶节点），需要在该连通分量内部(非割点处)放一个出口 cnt - 1
    • v-DCC度> 1，无需设置出口