柚子快報激活碼778899分享：圖論（強聯(lián)通分量）

http://yzkb.51969.com/

在圖論中，特別是在討論有向圖（Directed Graph）時，我們常常需要了解圖的結(jié)構特性，比如強聯(lián)通分量（Strongly Connected Components, SCC）。了解強聯(lián)通分量中的各種邊對于理解圖的整體結(jié)構以及某些算法（如Tarjan's算法或Kosaraju's算法）是非常重要的。以下是對強聯(lián)通分量及其邊類型的解釋：

強聯(lián)通分量（SCC）

強聯(lián)通分量是一個子圖，其中每對頂點之間都有路徑相互可達。換句話說，一個強聯(lián)通分量內(nèi)的任意兩個頂點 u?和 v?都滿足 u 到 v?和 v?到 u?之間存在路徑。

邊的分類

板子如下

#include

using namespace std;

const int N = 1e5 + 10;

vector e[N]; // 存儲圖的鄰接表

int dfn[N], low[N]; // 存儲每個節(jié)點的時間戳和最小到達時間

bool ins[N]; // 標記節(jié)點是否在棧中

int idx, bel[N], cnt; // 時間戳、節(jié)點所屬的強聯(lián)通分量編號、強聯(lián)通分量計數(shù)

stack stk; // 用于 Tarjan 算法的棧

vector> scc;// 存儲所有的強聯(lián)通分量

int n, m; // 節(jié)點數(shù)和邊數(shù)

void dfs(int u) {

dfn[u] = low[u] = ++idx; // 初始化時間戳

ins[u] = true; // 標記節(jié)點在棧中

stk.push(u); // 將節(jié)點壓入棧中

for (auto v : e[u]) { // 遍歷節(jié)點 u 的所有鄰接點 v

if (!dfn[v]) { // 如果節(jié)點 v 尚未訪問

dfs(v); // 遞歸訪問節(jié)點 v

low[u] = min(low[u], low[v]); // 更新節(jié)點 u 的最小到達時間

} else if (ins[v]) { // 如果節(jié)點 v 在棧中

low[u] = min(low[u], dfn[v]); // 更新節(jié)點 u 的最小到達時間

}

}

if (dfn[u] == low[u]) { // 如果節(jié)點 u 是強聯(lián)通分量的根節(jié)點

vector c; // 創(chuàng)建一個新的強聯(lián)通分量

++cnt;

while (1) {

int v = stk.top(); // 彈出棧頂節(jié)點

c.push_back(v); // 將節(jié)點添加到當前強聯(lián)通分量中

ins[v] = false; // 標記節(jié)點不在棧中

bel[v] = cnt; // 標記節(jié)點所屬的強聯(lián)通分量編號

stk.pop(); // 彈出棧頂節(jié)點

if (u == v) break; // 如果節(jié)點 u 是棧頂節(jié)點，結(jié)束循環(huán)

}

sort(c.begin(), c.end()); // 對強聯(lián)通分量內(nèi)的節(jié)點排序

scc.push_back(c); // 將強聯(lián)通分量添加到結(jié)果中

}

}

int main() {

ios::sync_with_stdio(0);

cin.tie(0);

cin >> n >> m;

for (int i = 1; i <= m; i++) {

int u, v;

cin >> u >> v;

e[u].push_back(v); // 構建鄰接表

}

for (int i = 1; i <= n; i++) {

if (!dfn[i]) dfs(i); // 對每個未訪問的節(jié)點進行 DFS

}

sort(scc.begin(), scc.end()); // 對所有的強聯(lián)通分量排序

cout << cnt << endl; // 輸出強聯(lián)通分量的數(shù)量

for (auto c : scc) { // 輸出每個強聯(lián)通分量

for (auto u : c) {

cout << u << " ";

}

cout << endl;

}

return 0;

}

題目鏈接?洛谷 B3609

參考文獻?scc

柚子快報激活碼778899分享：圖論（強聯(lián)通分量）

http://yzkb.51969.com/

好文鏈接