🔗 Cheatsheet: Strongly Connected Components (SCC)

📘 Giới thiệu

Một SCC (thành phần liên thông mạnh) trong đồ thị có hướng là tập hợp các đỉnh sao cho mỗi đỉnh đều có đường đi tới mọi đỉnh còn lại trong tập.

🧠 Ứng dụng

• Tối ưu hoá biểu đồ phụ thuộc.
• Rút gọn đồ thị (SCC DAG).
• Phát hiện chu trình trong đồ thị có hướng.
• Giải bài toán 2-SAT (sử dụng Kosaraju/Tarjan).
• Đếm số phần liên thông mạnh → mô hình hóa logic.

⏱️ Độ phức tạp

• Tarjan: O(V + E)
• Kosaraju: O(V + E)

✅ Ưu điểm

• Phân tích cấu trúc đồ thị có hướng hiệu quả.
• Cài đặt đơn giản, trực quan.
• Hỗ trợ rút gọn đồ thị để làm các bài toán cao hơn.

❌ Nhược điểm

• Chỉ áp dụng được cho đồ thị có hướng.
• Nếu cần tìm SCC lớn nhất / có điều kiện, cần xử lý thêm.

🚀 C++ Code (Tarjan’s Algorithm)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int tin[MAXN], low[MAXN], timer = 0;
bool on_stack[MAXN];
stack<int> st;
vector<vector<int>> sccs;

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

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

    if (low[u] == tin[u]) {
        vector<int> scc;
        int v;
        do {
            v = st.top(); st.pop();
            on_stack[v] = false;
            scc.push_back(v);
        } while (v != u);
        sccs.push_back(scc);
    }
}

void tarjan_scc(int n) {
    fill(tin, tin + n + 1, 0);
    fill(low, low + n + 1, 0);
    fill(on_stack, on_stack + n + 1, false);
    timer = 0;
    while (!st.empty()) st.pop();
    sccs.clear();

    for (int i = 1; i <= n; ++i)
        if (!tin[i]) dfs(i);
}

🧭 Khi nào dùng?

🔧 Tối ưu khi dùng

• Với Kosaraju, cần đồ thị đảo chiều (transposed) → chiếm thêm bộ nhớ.
• Với Tarjan, chỉ cần 1 DFS → hiệu quả cho đồ thị lớn.
• Khi cần DAG SCC: gán id mỗi SCC và rút gọn đồ thị theo id.
• Lưu id[u]: id của SCC mà đỉnh u thuộc về.

📚 Tham khảo

• CP-Algorithms - Strongly Connected Components
• CSES Problem Set: Flight Routes Check / Giant Pizza
• Codeforces 371C, 427C, AtCoder ABC231 Ex