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

http://yzkb.51969.com/

在圖論中，特別是在討論有向圖（Directed Graph）時(shí)，我們常常需要了解圖的結(jié)構(gòu)特性，比如強(qiáng)聯(lián)通分量（Strongly Connected Components, SCC）。了解強(qiáng)聯(lián)通分量中的各種邊對(duì)于理解圖的整體結(jié)構(gòu)以及某些算法（如Tarjan's算法或Kosaraju's算法）是非常重要的。以下是對(duì)強(qiáng)聯(lián)通分量及其邊類(lèi)型的解釋?zhuān)?/p>

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

強(qiáng)聯(lián)通分量是一個(gè)子圖，其中每對(duì)頂點(diǎn)之間都有路徑相互可達(dá)。換句話說(shuō)，一個(gè)強(qiáng)聯(lián)通分量?jī)?nèi)的任意兩個(gè)頂點(diǎn) u?和 v?都滿(mǎn)足 u 到 v?和 v?到 u?之間存在路徑。

邊的分類(lèi)

板子如下

#include

using namespace std;

const int N = 1e5 + 10;

vector e[N]; // 存儲(chǔ)圖的鄰接表

int dfn[N], low[N]; // 存儲(chǔ)每個(gè)節(jié)點(diǎn)的時(shí)間戳和最小到達(dá)時(shí)間

bool ins[N]; // 標(biāo)記節(jié)點(diǎn)是否在棧中

int idx, bel[N], cnt; // 時(shí)間戳、節(jié)點(diǎn)所屬的強(qiáng)聯(lián)通分量編號(hào)、強(qiáng)聯(lián)通分量計(jì)數(shù)

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

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

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

void dfs(int u) {

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

ins[u] = true; // 標(biāo)記節(jié)點(diǎn)在棧中

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

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

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

dfs(v); // 遞歸訪問(wèn)節(jié)點(diǎn) v

low[u] = min(low[u], low[v]); // 更新節(jié)點(diǎn) u 的最小到達(dá)時(shí)間

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

low[u] = min(low[u], dfn[v]); // 更新節(jié)點(diǎn) u 的最小到達(dá)時(shí)間

}

}

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

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

++cnt;

while (1) {

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

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

ins[v] = false; // 標(biāo)記節(jié)點(diǎn)不在棧中

bel[v] = cnt; // 標(biāo)記節(jié)點(diǎn)所屬的強(qiáng)聯(lián)通分量編號(hào)

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

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

}

sort(c.begin(), c.end()); // 對(duì)強(qiáng)聯(lián)通分量?jī)?nèi)的節(jié)點(diǎn)排序

scc.push_back(c); // 將強(qiáng)聯(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); // 構(gòu)建鄰接表

}

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

if (!dfn[i]) dfs(i); // 對(duì)每個(gè)未訪問(wèn)的節(jié)點(diǎn)進(jìn)行 DFS

}

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

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

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

for (auto u : c) {

cout << u << " ";

}

cout << endl;

}

return 0;

}

題目鏈接?洛谷 B3609

參考文獻(xiàn)?scc

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

http://yzkb.51969.com/

好文鏈接