Strongly Connected Components

Pada graph tak berarah, connected component adalah kelompok node yang saling terhubung. Namun pada graph berarah, konsep “terhubung” menjadi lebih halus: node u dapat mencapai v belum berarti v dapat mencapai u. Strongly Connected Component (SCC) adalah kelompok node di mana setiap pasangan saling terjangkau — u dapat ke v dan v dapat ke u untuk semua pasangan dalam kelompok. Konsep ini muncul di mana-mana: analisis dependensi modul software (cycle = bug), pemecahan automata state menjadi komponen minimal, dan optimasi compiler. Pada Chapter ini kita akan membedah dua algoritma klasik: Kosaraju (2x DFS sederhana) dan Tarjan (DFS tunggal dengan lowlink), serta mengimplementasikannya dalam C++.

Aturan: Komponen Saling Terjangkau #

Pada graph berarah G, SCC adalah partisi node maksimal sehingga untuk setiap pasangan u, v dalam satu komponen, terdapat path u → v dan path v → u. SCC membentuk partisi — setiap node termasuk tepat satu SCC.

Konsep kunci: condensation graph (DAG of SCC). Bila setiap SCC diciutkan menjadi satu node, hasilnya adalah DAG — tidak ada siklus antar SCC (kalau ada, keduanya sebenarnya satu SCC).

Mekanisme 1: Kosaraju (2x DFS) #

Idenya elegan:

DFS pertama pada G: catat urutan post-order — node yang selesai diproses lebih dulu muncul lebih awal.
Transpose graph: balik semua edge → G^T.
DFS kedua pada G^T dalam urutan reverse post-order (dari node yang selesai terakhir di DFS pertama). Setiap tree yang dihasilkan adalah satu SCC.

Kenapa ini bekerja? Node yang selesai paling akhir di DFS pertama ada di “source” SCC pada condensation DAG — yang tidak bisa dijangkau dari SCC lain. Pada G^T, “source” SCC menjadi “sink” — DFS dari sana hanya menjelajah node dalam SCC yang sama.

flowchart TD A["DFS pass 1 pada G<br/>catat post-order"] --> B["Transpose: G -> G^T"] B --> C["DFS pass 2 pada G^T<br/>reverse post-order"] C --> D["Setiap tree = satu SCC"]

Mekanisme 2: Tarjan (DFS Tunggal dengan Lowlink) #

Tarjan menggunakan satu DFS dengan dua array:

disc[u] = discovery time (urutan kunjungan).
low[u] = disc minimum yang dapat dicapai dari subtree u melalui paling banyak satu back edge.

Selama DFS, simpan stack node yang sedang “dalam proses” (root kandidat SCC). Saat disc[u] == low[u] (u adalah root SCC), pop stack sampai u dikeluarkan — semua node yang di-pop adalah satu SCC.

Implementasi Kosaraju #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

class Graph {
    int n;
    std::vector<std::vector<int>> adj, radj;
public:
    explicit Graph(int n) : n(n), adj(n), radj(n) {}
    void add_edge(int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    // === Kosaraju: 2x DFS ===
    std::vector<std::vector<int>> kosaraju() {
        std::vector<bool> visited(n, false);
        std::vector<int> order;
        // Pass 1: DFS pada G, simpan post-order
        for (int u = 0; u < n; ++u)
            if (!visited[u]) dfs1(u, visited, order);

        // Pass 2: DFS pada G^T dalam reverse post-order
        std::vector<int> comp(n, -1);
        std::vector<std::vector<int>> sccs;
        for (int i = n - 1; i >= 0; --i) {
            int u = order[i];
            if (comp[u] == -1) {
                sccs.emplace_back();
                dfs2(u, comp, sccs.back());
            }
        }
        return sccs;
    }

private:
    void dfs1(int u, std::vector<bool>& visited, std::vector<int>& order) {
        visited[u] = true;
        for (int v : adj[u])
            if (!visited[v]) dfs1(v, visited, order);
        order.push_back(u); // post-order
    }
    void dfs2(int u, std::vector<int>& comp, std::vector<int>& cur) {
        comp[u] = (int)cur.size();
        cur.push_back(u);
        for (int v : radj[u])
            if (comp[v] == -1) dfs2(v, comp, cur);
    }
};

int main() {
    // Graph berarah dengan 3 SCC:
    //   SCC1: {0, 1, 2} membentuk siklus
    //   SCC2: {3, 4} membentuk siklus
    //   SCC3: {5} sendiri
    //   Edge antar SCC: 2->3, 4->5
    Graph g(6);
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    g.add_edge(2, 0);  // siklus 0-1-2-0
    g.add_edge(2, 3);  // ke SCC2
    g.add_edge(3, 4);
    g.add_edge(4, 3);  // siklus 3-4-3
    g.add_edge(4, 5);  // ke SCC3

    auto sccs = g.kosaraju();
    std::cout << "Strongly Connected Components (Kosaraju):\n";
    std::cout << "  Total SCC: " << sccs.size() << "\n";
    for (size_t i = 0; i < sccs.size(); ++i) {
        std::cout << "  SCC " << i << ": {";
        for (size_t j = 0; j < sccs[i].size(); ++j) {
            if (j) std::cout << ", ";
            std::cout << sccs[i][j];
        }
        std::cout << "}\n";
    }
    return 0;
}

Output yang Dihasilkan:

text
Strongly Connected Components (Kosaraju):
  Total SCC: 3
  SCC 0: {0, 2, 1}
  SCC 1: {3, 4}
  SCC 2: {5}

Bedah Kode Baris-per-Baris #

std::vector<std::vector<int>> adj, radj: adjacency list untuk graph asli G dan transpose G^T. Keduanya dibangun bersamaan saat add_edge dipanggil.
radj[v].push_back(u): saat edge u → v ditambahkan ke adj, edge v → u otomatis ditambahkan ke radj. Inilah operasi transpose.
std::vector<int> order: list yang menyimpan urutan post-order dari DFS pertama. Node yang selesai lebih dulu di-append lebih awal.
dfs1(u, visited, order): DFS biasa. Setelah semua descendant u selesai, u di-append ke order. Inilah post-order.
for (int i = n - 1; i >= 0; --i): iterasi order dari belakang (reverse post-order). Node yang selesai paling akhir di DFS pertama diproses pertama di DFS kedua.
if (comp[u] == -1): skip node yang sudah termasuk SCC. Hanya jadi root DFS kedua bila belum di-assign ke komponen manapun.
dfs2(u, comp, sccs.back()): DFS pada G^T (radj). Setiap tree yang dihasilkan adalah satu SCC. comp[u] diisi index lokal dalam SCC.
for (int v : radj[u]): ikuti edge pada G^T — yang aslinya edge masuk ke u pada G. Inilah kunci: DFS pada G^T hanya bisa keluar dari SCC root via edge yang ada di dalam SCC (karena edge antar SCC di G menjadi edge masuk ke SCC source, bukan keluar).
Hasil: 3 SCC ditemukan — {0, 2, 1} (urutan dalam DFS post-order), {3, 4}, {5}. Set berisi node yang saling terjangkau dalam graph asli.

Trace Kosaraju Step-by-Step #

Pass 1 (DFS pada G):

Step	DFS dari	Path	Post-order (urutan append)
1	0	0 → 1 → 2 → 0 (visited)	2, 1, 0
2	(semua visited)	—	—
3	3 (unvisited dari iterasi 0..5)	3 → 4 → 3 (visited), 4 → 5	5, 4, 3

order = [2, 1, 0, 5, 4, 3]. Reverse post-order = [3, 4, 5, 0, 1, 2].

Pass 2 (DFS pada G^T):

Step	Mulai dari	DFS di `G^T`	SCC
1	3	3 ← 4 (di G), 4 ← 3 di G^T = 4→3 di G. Edge 4→3 ada. Tetangga 3 di G^T: yang punya edge ke 3 di G = node 4 (edge 4→3) dan node 2 (edge 2→3). DFS: 3 → 4 → 3 (visited). Tetangga 4 di G^T: node 3 (edge 3→4) dan node 5? Tidak, edge 5→4 tidak ada. Hanya 3.	`{3, 4}`
2	5	Tetangga 5 di G^T: yang punya edge ke 5 di G = node 4 (edge 4→5). Tapi 4 sudah di SCC lain.	`{5}`
3	0	Tetangga 0 di G^T: yang punya edge ke 0 di G = node 2 (edge 2→0). DFS: 0 → 2 → 1 → 0 (visited).	`{0, 2, 1}`

Hasil: 3 SCC dengan total bobot semua node = 6 = V. ✓

Implementasi Tarjan (Sketsa) #

cpp
class TarjanGraph {
    int n, timer = 0;
    std::vector<std::vector<int>> adj;
    std::vector<int> disc, low;
    std::vector<bool> on_stack;
    std::stack<int> st;
    std::vector<std::vector<int>> sccs;

public:
    explicit TarjanGraph(int n) : n(n), adj(n), disc(n, -1), low(n, -1), on_stack(n, false) {}
    void add_edge(int u, int v) { adj[u].push_back(v); }

    std::vector<std::vector<int>> tarjan() {
        for (int u = 0; u < n; ++u)
            if (disc[u] == -1) dfs(u);
        return sccs;
    }

private:
    void dfs(int u) {
        disc[u] = low[u] = timer++;
        st.push(u); on_stack[u] = true;
        for (int v : adj[u]) {
            if (disc[v] == -1) {
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (on_stack[v]) {
                low[u] = std::min(low[u], disc[v]);
            }
        }
        if (low[u] == disc[u]) {
            sccs.emplace_back();
            int v;
            do {
                v = st.top(); st.pop();
                on_stack[v] = false;
                sccs.back().push_back(v);
            } while (v != u);
        }
    }
};

Penjelasan Tarjan Singkat #

disc[u]: discovery time. Saat node pertama kali dikunjungi.
low[u]: minimum disc yang dapat dicapai u melalui subtree-nya + satu back edge.
on_stack[u]: penanda node masih di stack (calon anggota SCC saat ini).
if (low[u] == disc[u]): u adalah root SCC — semua node di stack sampai u adalah satu SCC. Pop dan catat.
Back edge ke node yang on_stack: artinya ada jalur balik ke ancestor SCC → perbarui low.

Komparasi Kosaraju vs Tarjan #

Aspek	Kosaraju	Tarjan
Jumlah DFS	2 (G dan G^T)	1 (DFS tunggal)
Memori	2× adjacency list	1× adjacency list + stack + disc/low
Kompleksitas	`O(V + E)`	`O(V + E)`
Implementasi	Lebih mudah dipahami	Lebih ringkas
Constant factor	Sedikit lebih besar (2× DFS)	Lebih kecil

Aplikasi Nyata #

Dependency cycle detection: cycle pada modul/package dependency graph = error build.
2-SAT solver: variabel boolean + clause OR-of-2 → graph implikasi → SCC → penyelesaian.
Control flow analysis (compiler): loop detection pada CFG melalui SCC.
Markov chain aggregation: state yang saling terjangkau = agregat.
Social network analysis: kelompok user yang saling mention = SCC.

Kompleksitas #

Aspek	Kosaraju	Tarjan
Waktu	`O(V + E)`	`O(V + E)`
Ruang	`O(V + E)` (2 adj list)	`O(V + E)` (1 adj list + stack)
Recursion depth	`O(V)` pada call stack	`O(V)` pada call stack

Ringkasan #

SCC adalah partisi node maksimal di mana setiap pasangan saling terjangkau pada graph berarah.
Kosaraju: DFS pertama pada G untuk post-order, DFS kedua pada G^T dalam reverse post-order.
Tarjan: DFS tunggal dengan disc[]/low[] + stack; root SCC saat disc[u] == low[u].
Condensation graph (DAG of SCC) tidak punya siklus.
Aplikasi: dependency cycle, 2-SAT, compiler loop detection, social network analysis.

Bab berikutnya akan membahas Articulation Points dan Bridges — bagaimana menemukan node dan edge kritis yang menghapusnya memutus graph.