Strongly Connected Components (SCC)

Wiki › Thuật toán › Thuật toán đồ thị

huunguyen · Last updated 8, Tháng 4, 2026, 15:25

Strongly Connected Component (SCC) của đồ thị có hướng là tập đỉnh tối đại mà từ bất kỳ đỉnh nào trong tập cũng có thể đi đến bất kỳ đỉnh nào khác trong tập.

Sau khi thu gọn mỗi SCC thành một siêu đỉnh, đồ thị trở thành DAG (đồ thị có hướng không chu trình) — gọi là condensation graph.

Thuật toán Kosaraju — $O (V + E)$

Hai lần DFS:

DFS trên đồ thị gốc, lưu thứ tự kết thúc vào stack.
DFS trên đồ thị đảo chiều theo thứ tự ngược stack — mỗi lần DFS tìm được một SCC.

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN], radj[MAXN];
bool visited[MAXN];
int comp[MAXN];   // comp[u] = chỉ số SCC của u
stack<int> order;

void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfs1(v);
    order.push(u);
}

void dfs2(int u, int c) {
    comp[u] = c;
    for (int v : radj[u]) if (comp[v] == -1) dfs2(v, c);
}

int kosaraju(int n) {
    fill(visited, visited+n+1, false);
    fill(comp, comp+n+1, -1);

    for (int i = 1; i <= n; i++) if (!visited[i]) dfs1(i);

    int num_scc = 0;
    while (!order.empty()) {
        int u = order.top(); order.pop();
        if (comp[u] == -1) dfs2(u, num_scc++);
    }
    return num_scc;   // số lượng SCC
}

Thuật toán Tarjan — $O (V + E)$

Một lần DFS duy nhất, dùng stack và low values:

int disc[MAXN], low[MAXN], timer_val = 0;
bool on_stack[MAXN];
stack<int> st;
int comp[MAXN], num_scc = 0;

void dfs(int u) {
    disc[u] = low[u] = ++timer_val;
    st.push(u); on_stack[u] = true;

    for (int v : adj[u]) {
        if (!disc[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }

    // u là gốc của một SCC
    if (low[u] == disc[u]) {
        while (true) {
            int v = st.top(); st.pop();
            on_stack[v] = false;
            comp[v] = num_scc;
            if (v == u) break;
        }
        num_scc++;
    }
}

// Gọi: for (int i = 1; i <= n; i++) if (!disc[i]) dfs(i);

Lưu ý: Tarjan đánh số SCC theo thứ tự ngược topo (SCC được tìm trước có chỉ số nhỏ hơn, nhưng đứng sau trong topo sort của condensation graph).

Condensation Graph

Sau khi tìm SCC, xây DAG của các SCC:

// Xây condensation graph
vector<int> dag[MAXN];
set<pair<int,int>> added;

for (int u = 1; u <= n; u++)
    for (int v : adj[u])
        if (comp[u] != comp[v] && !added.count({comp[u], comp[v]})) {
            dag[comp[u]].push_back(comp[v]);
            added.insert({comp[u], comp[v]});
        }

So sánh Kosaraju và Tarjan

	Kosaraju	Tarjan
Số lần DFS	2	1
Cần đồ thị đảo chiều	Có	Không
Cài đặt	Đơn giản hơn	Phức tạp hơn một chút
Hiệu năng	Tương đương	Tương đương

Khi nào dùng SCC?

Phát hiện chu trình trong đồ thị có hướng.
Rút gọn đồ thị thành DAG để áp dụng DP/Topo sort.
Bài toán 2-SAT (mỗi clause tương đương cạnh có hướng, SCC xác định nghiệm).
Bài toán reachability: từ SCC nào có thể đến SCC nào.

Bình luận

Không có bình luận tại thời điểm này.