08.19总结

连通性

在无向图中，若任意两点间均存在路径相连，则该图称为连通图。
若删除图中任意一个顶点后，剩余图仍保持连通性，则该图为点双连通图。
若删除图中任意一条边后，图仍保持连通性，则该图为边双连通图。
在有向图中，若将所有有向边视为无向边后得到的图是连通的，则称该图为弱连通图。
若在有向图中任意两点间均存在双向可达路径，则该图称为强连通图。

强连通分量

强连通分量（Strongly Connected Components，简称SCC）是指图中的极大强连通子图。

在有向图的 DFS 生成树中，存在四种类型的边：

1. 树边：黑色实线，表示从父节点指向未被访问的子节点
2. 返祖边：红色虚线，指向祖先节点的边
3. 前向边：绿色虚线，指向子树中节点的边
4. 横叉边：蓝色虚线，指向已访问过且既非祖先也非子树中的节点

需要注意的是，前向边和横叉边仅存在于有向图的DFS生成树中，而无向图只有树边和返祖边。
关于 DFS 生成树与强连通分量(SCC)的关系：

• 在某个 SCC 中，最先被访问的节点 $u$ 具有重要特性
• 该 SCC 中其他所有节点必定位于以 $u$为根的子树中

证明过程如下：
假设 SCC 中存在节点 $v$ 不在 $u$ 的子树中：
从 $u$ 到 $v$ 的路径必然包含离开该子树的边（横叉边或返祖边）
这类边指向的节点必须已被访问过
由于 $u$ 和 $v$ 属于一个SCC，访问这些更早被访问的节点时应该能到达$u$
这与u是最先被访问的前提矛盾，故假设不成立。

实现

void tarjan(int u) {low[u] = dfn[u] = ++tot;sta.push(u);in[u] = 1;for (auto v : ve[u]) {if (!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]);} else if (in[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {vector <int> vnow;while (vnow.empty() || vnow.back() != u) {vnow.push_back(sta.top());in[sta.top()] = 0;sta.pop();}scc.push_back(vnow);}
}

缩点

在图论问题中，我们可以将强连通分量(SCC)缩成一个节点，从而将原图转化为有向无环图(DAG)。在进行缩点操作时，需要特别注意原图与新图中边的对应关系。

边双连通分量

将强连通分量中的有向边替换为无向边后，就形成了边双连通分量。这是因为在强连通分量中，任意两点 $u$ 和 $v$ 之间都存在 $u$ 到 $v$ 和 $v$ 到 $u$ 的路径。当转换为无向边时，这些路径保证了任意两点之间至少存在两条不同的路径连接，这正是边双连通分量 (BCC) 的定义特征。

实现

void tarjan(int u, int fa) {low[u] = dfn[u] = ++tot;sta.push(u);in[u] = 1;int mark = 0;for (auto v : ve[u]) {if (v == fa) {if (!mark) {mark = 1;} else {low[u] = min(low[u], dfn[v]);}continue;}if (!dfn[v]) {tarjan(v, u);low[u] = min(low[u], low[v]);} else {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {vector <int> vnow;while (vnow.empty() || vnow.back() != u) {vnow.push_back(sta.top());in[sta.top()] = 0;sta.pop();}bcc.push_back(vnow);}
}