連通性

在無向圖中，若任意兩點間均存在路徑相連，則該圖稱為連通圖。
若刪除圖中任意一個頂點后，剩余圖仍保持連通性，則該圖為點雙連通圖。
若刪除圖中任意一條邊后，圖仍保持連通性，則該圖為邊雙連通圖。
在有向圖中，若將所有有向邊視為無向邊后得到的圖是連通的，則稱該圖為弱連通圖。
若在有向圖中任意兩點間均存在雙向可達路徑，則該圖稱為強連通圖。

強連通分量

強連通分量（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);}
}