连通相关问题

首先介绍几个前置概念（关于 DFS 的）。我们在对一个图进行 DFS 时，搜索的路径是一棵树，称为 DFS 生成树。基于此，整个图的边可以分为以下几种：

• 树边。也就是在 DFS 生成树上的边。

• 非树边。顾名思义，就是不在生成树上的边。又分为：

  • 前向边：一个节点指向它子树中的节点（但是不是树边）。
  • 返祖边：一个节点指向它祖先的祖先。
  • 横叉边：边的两个端点没有祖先-后代关系。

强连通分量

强连通指的是：在有向图中，$u,v$ 是图中节点，如果 $u\to v$ 和 $v\to u$ 这两条路径都存在，就称 $u,v$ 两点强连通。

强连通分量（Strongly Connected Components，SCC），指的是：图中极大的强连通子图。SSC有三种算法求解：

• Tarjan

• Kosaraju

• Garbow

时间复杂度都是 $O(n+m)$。

什么是 “极大”？

“极大” 和 “最大” 不同。一个图的 “极大” 的强连通子图（们）是互不相交的，其并集就是原图（如果把单点也看做强连通），也就可以看做是对原图的分割。

双连通分量

双连通有两种（在无向图中）：

• $u,v$ 是图中连通的两点，如果删去任意一条图中的边都不能破坏它们的连通性，就称它们边双连通。

  边双连通具有传递性：$a,b$ 强连通，$b,c$ 强连通，则 $a,c$ 强连通。

• $u,v$ 是图中连通的两点，如果删去任意一个图中的点（不包含 $u,v$）都不能破坏它们的连通性，就称它们点双连通。

  点双连通不具有传递性。

同样地，双连通分量也有两种：

• 边强连通分量：图中极大的子图，使得任意节点之间边双联通。

• 点强连通分量：图中极大的子图，使得任意节点之间点双联通。

边双联通同样用 Tarjan 算法求。

割点 & 割边

• 割点：对于一个连通无向图，如果删去一个点 $u$，使得这个图的连通性被破坏，就称 $u$ 为割点。

• 割边：对于一个连通无向图，如果删去一条边 $e$，使得这个图的连通性被破坏，就称 $e$ 为割边，又称为桥。

割点和割边也可以用 Tarjan 算法求。

二分图

如果一个图 $G(V,E)$ 可以分为两个互不相交的点集合 $V_1,V_2$，且 $V_1\cup V_2=V$，且 $V_1$、$V_2$ 内部的节点互相没有直接的边连接，就说 $G$ 是一个二分图。