Wiki › Thuật toán › Thuật toán đồ thị › Strongly Connected Components (SCC)

Strongly Connected Components (SCC)

huunguyen Updated Tháng sáu 2, 2026

Thành phần liên thông mạnh (Strongly Connected Component — SCC) của một đồ thị có hướng là một tập đỉnh tối đại sao cho từ bất kỳ đỉnh nào trong tập cũng đi đến được mọi đỉnh khác trong tập (và ngược lại). Nói cách khác, mọi cặp đỉnh trong cùng một SCC nằm trên ít nhất một chu trình chung.

Tìm tất cả SCC cho phép thu gọn (nén) đồ thị thành một DAG (đồ thị có hướng không chu trình) — gọi là đồ thị nén (condensation graph) — chỉ trong $O (V + E)$ , thay vì phải duyệt reachability $O (V \cdot (V + E))$ cho từng đỉnh. Đây là bước tiền xử lý chủ lực cho hàng loạt bài: phát hiện chu trình, 2-SAT, đếm số đỉnh đến được, DP trên đồ thị có chu trình...

Ý tưởng / Trực giác

Quan hệ " $u$ và $v$ đến được nhau" là một quan hệ tương đương (phản xạ, đối xứng, bắc cầu), nên nó chia tập đỉnh thành các lớp rời nhau — chính là các SCC. Khi gom mỗi SCC thành một "siêu đỉnh", đồ thị mới không thể còn chu trình: nếu siêu đỉnh $A$ đến được $B$ và $B$ đến được $A$ thì mọi đỉnh của $A$ và $B$ đến được nhau, mâu thuẫn với việc chúng là hai SCC khác nhau. Vì vậy đồ thị nén luôn là DAG.

Có hai thuật toán kinh điển, cùng độ phức tạp $O (V + E)$ :

Kosaraju dựa trên một quan sát đẹp: nếu ta xử lý các đỉnh theo thứ tự kết thúc DFS giảm dần trên đồ thị gốc, rồi chạy DFS trên đồ thị đảo chiều, thì mỗi lần DFS sẽ "kẹt" lại đúng trong một SCC. Lý do: đỉnh có thời điểm kết thúc lớn nhất nằm trong SCC là "nguồn" của đồ thị nén; trên đồ thị đảo chiều, SCC nguồn trở thành SCC đích, nên DFS từ đỉnh đó không thoát ra ngoài SCC chứa nó.

Tarjan chỉ cần một lần DFS. Với mỗi đỉnh $u$ ta lưu disc[u] (thời điểm thăm lần đầu) và low[u] = disc nhỏ nhất có thể chạm tới từ cây con của $u$ qua các cạnh hợp lệ. Một đỉnh $u$ là gốc của một SCC khi low[u] == disc[u]: nghĩa là cây con của $u$ không có cách nào "vòng" lên trên $u$ qua một đỉnh đang còn trên stack. Khi đó tất cả đỉnh còn nằm trên stack tính từ $u$ trở xuống tạo thành một SCC.

Điểm tinh tế của Tarjan: chỉ cập nhật low[u] từ cạnh ngược/cạnh chéo (u,v) khi $v$ vẫn còn trên stack (on_stack[v]). Nếu $v$ đã được gán SCC và rời stack, cạnh đó đi sang SCC khác và không được phép kéo low[u] xuống — nếu không ta sẽ gộp nhầm hai SCC làm một.

Ví dụ chạy tay (Tarjan)

Xét đồ thị 5 đỉnh, các cạnh: $1 \to 2, 2 \to 3, 3 \to 1, 3 \to 4, 4 \to 5$ .

   1 ──▶ 2
   ▲     │
   │     ▼
   3 ◀───┘
   │
   ▼
   4 ──▶ 5

Chu trình $1 \to 2 \to 3 \to 1$ tạo thành một SCC; đỉnh $4$ và $5$ mỗi đỉnh là một SCC riêng. Chạy DFS từ đỉnh 1, dùng timer tăng dần. Bảng dưới đánh dấu * ở dòng vừa cập nhật:

Bước                         disc low  stack            ghi chú
thăm 1   disc=low=1          [1]  [1]  1
thăm 2   disc=low=2          [_,2][_,2] 1 2
thăm 3   disc=low=3          ...  ...   1 2 3
  cạnh 3->1: 1 còn trên stack
        low[3]=min(3,disc1=1)=1 *      1 2 3        kéo low[3] xuống 1
  cạnh 3->4:
thăm 4   disc=low=4                    1 2 3 4
thăm 5   disc=low=5                    1 2 3 4 5
    5 không có cạnh ra
    low[5]=disc[5]=5  ──▶ POP {5}  => SCC #0 = {5}
  quay về 4: low[4]=min(4,low5=5)=4
    low[4]=disc[4]=4  ──▶ POP {4}  => SCC #1 = {4}
  quay về 3: low[3]=1 ≠ disc[3]=3  (chưa phải gốc, không pop)
  quay về 2: low[2]=min(2,low3=1)=1 *
  quay về 1: low[1]=min(1,low2=1)=1
    low[1]=disc[1]=1  ──▶ POP {3,2,1} => SCC #2 = {1,2,3}

Giá trị low cuối cùng:

đỉnh	1	2	3	4	5
disc	1	2	3	4	5
low	1	1	1	4	5

Ba đỉnh có low == disc (1, 4, 5) chính là ba gốc SCC. Kết quả: ${5}, {4}, {1, 2, 3}$ . Lưu ý SCC được "đóng" theo thứ tự ngược topo — SCC ${5}$ (cuối DAG) ra trước, SCC ${1, 2, 3}$ (đầu DAG) ra sau cùng.

Cài đặt

Tarjan (một lần DFS)

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], comp[MAXN];
bool on_stack[MAXN];
int timer_val = 0, num_scc = 0;
stack<int> st;

void dfs(int u) {
    disc[u] = low[u] = ++timer_val;   // thời điểm thăm = giá trị low ban đầu
    st.push(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (!disc[v]) {               // cạnh cây: đi sâu rồi cập nhật low
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {      // cạnh ngược/chéo NHƯNG v còn trên stack
            low[u] = min(low[u], disc[v]);  // dùng disc[v], KHÔNG dùng low[v]
        }
        // nếu v đã rời stack -> cạnh sang SCC khác, bỏ qua
    }

    if (low[u] == disc[u]) {           // u là gốc của một SCC
        while (true) {
            int v = st.top(); st.pop();
            on_stack[v] = false;
            comp[v] = num_scc;         // gán nhãn SCC (thứ tự ngược topo)
            if (v == u) break;
        }
        num_scc++;
    }
}

// Gọi cho mọi đỉnh chưa thăm:
// for (int i = 1; i <= n; i++) if (!disc[i]) dfs(i);

Kosaraju (hai lần DFS — dễ nhớ hơn)

vector<int> adj[MAXN], radj[MAXN];   // adj: gốc, radj: đảo chiều
bool visited[MAXN];
int comp[MAXN];
stack<int> order;

void dfs1(int u) {                    // lượt 1: lưu thứ tự kết thúc
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfs1(v);
    order.push(u);                    // u kết thúc -> đẩy vào stack
}

void dfs2(int u, int c) {             // lượt 2: trên đồ thị đảo chiều
    comp[u] = c;
    for (int v : radj[u]) if (comp[v] == -1) dfs2(v, c);
}

int kosaraju(int n) {
    fill(visited + 1, visited + n + 1, false);
    fill(comp + 1, comp + n + 1, -1);
    for (int i = 1; i <= n; i++) if (!visited[i]) dfs1(i);

    int num_scc = 0;
    while (!order.empty()) {          // duyệt theo thứ tự kết thúc giảm dần
        int u = order.top(); order.pop();
        if (comp[u] == -1) dfs2(u, num_scc++);
    }
    return num_scc;
}

Xây đồ thị nén (condensation)

vector<int> dag[MAXN];
set<pair<int,int>> added;            // tránh cạnh bội giữa hai SCC

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

Độ phức tạp

Thời gian: $O (V + E)$ . Cả Kosaraju lẫn Tarjan đều chỉ duyệt mỗi đỉnh và mỗi cạnh một số lần hằng (Kosaraju duyệt hai lần, Tarjan một lần) — hệ số khác nhau nhưng cùng bậc. Việc pop stack ở Tarjan: mỗi đỉnh được push và pop đúng một lần, tổng $O (V)$ .
Bộ nhớ: $O (V + E)$ . Danh sách kề chiếm $O (V + E)$ . Tarjan thêm các mảng disc, low, comp, on_stack cùng một stack — tất cả $O (V)$ . Kosaraju cần thêm đồ thị đảo chiều radj, tốn thêm $O (V + E)$ bộ nhớ.
Xây đồ thị nén bằng set mất $O (E \log E)$ ; muốn $O (V + E)$ có thể dùng cách đánh dấu cạnh trùng theo từng SCC.

⚠️ Lỗi thường gặp

Tarjan: dùng low[v] thay vì disc[v] cho cạnh ngược. Khi gặp cạnh (u,v) mà $v$ còn trên stack, phải cập nhật low[u] = min(low[u], disc[v]). Dùng low[v] vẫn "thường" cho kết quả đúng số SCC nhưng phá vỡ ngữ nghĩa low và có thể sai trong các biến thể (vd tìm cầu/khớp). Hãy bám đúng disc[v].
Quên kiểm tra on_stack[v]. Nếu $v$ đã được gán SCC khác và rời stack, mà ta vẫn kéo low[u] xuống theo nó, thì hai SCC khác nhau sẽ bị gộp nhầm thành một. Triệu chứng: số SCC ít hơn thực tế.
Đệ quy DFS gây tràn stack với $N$ lớn. Với $N$ đến $10^{5}$ – $2 \cdot 10^{5}$ , DFS đệ quy dễ stack overflow (runtime error). Khắc phục: tăng giới hạn stack, hoặc viết DFS lặp dùng stack tường minh.
Quên gọi DFS cho mọi đỉnh. Đồ thị có thể không liên thông; phải lặp for i in 1..n: if chưa thăm thì dfs(i), nếu chỉ chạy từ đỉnh 1 sẽ bỏ sót cả mảng đồ thị.
Nhầm chiều thứ tự SCC khi cần thứ tự topo. Tarjan đánh số SCC theo ngược topo (SCC tìm trước có chỉ số nhỏ nhưng đứng sau trong DAG). Nếu bài cần DP theo thứ tự topo của đồ thị nén, hãy duyệt nhãn comp giảm dần, hoặc đảo lại nhãn, đừng giả định nhãn tăng dần là thứ tự topo.
Quên khử cạnh bội / khuyên khi nén. Bỏ qua điều kiện comp[u] != comp[v] sẽ thêm khuyên (cạnh tự nối) vào đồ thị nén; không khử cạnh trùng có thể làm phình bộ nhớ và sai khi đếm bậc.

Biến thể / Mở rộng

2-SAT: mỗi biến $x$ ứng với hai đỉnh $x$ và $\neg x$ ; mệnh đề $(a \lor b)$ thành hai cạnh kéo theo. Hệ có nghiệm khi và chỉ khi không biến nào cùng SCC với phủ định của nó; gán giá trị theo thứ tự topo của đồ thị nén.
Đếm reachability: sau khi nén thành DAG, dùng DP hoặc bitset trên thứ tự topo để đếm số đỉnh/SCC đến được — nhanh hơn nhiều so với BFS từ từng đỉnh.
Phát hiện chu trình có hướng: đồ thị có chu trình khi và chỉ khi tồn tại một SCC có kích thước $\geq 2$ (hoặc một đỉnh có cạnh tự lặp).

Bài tập luyện

Thành phố liên thông mạnh (sccity) — (Trung cấp) Dựng đồ thị có hướng từ lưới đường rồi kiểm tra toàn đồ thị có phải một SCC duy nhất hay không — bài nhập môn đúng định nghĩa SCC.
Cánh đồng cỏ (grasscow) — (Kỳ cựu) Nén SCC thành DAG rồi DP đường đi dài nhất khi được phép đảo ngược đúng một cạnh — bài kinh điển về condensation + DP trên DAG.
Truy vấn khả năng đến được (reachqry) — (Chuyên gia) Trả lời nhiều truy vấn reachability trên đồ thị có hướng tổng quát; nén SCC thành DAG rồi dùng bitset trên thứ tự topo để gộp các đỉnh trong cùng chu trình.