ตรวจสอบ Strongly Connected Graph ด้วย Kosaraju Algorithm (DFS) ใน C++

Directed Graph เป็น Strongly Connected ก็ต่อเมื่อทุกคู่โหนด (u,v) มี Path u→v และ v→u

Kosaraju Algorithm (2-pass DFS)

1. DFS จากโหนด 0 บน Graph เดิม → ต้อง Visit ทุกโหนด
2. Reverse ทุก Edge (Transpose Graph)
3. DFS จากโหนด 0 บน Graph ที่ Reverse → ต้อง Visit ทุกโหนด
4. ทั้งคู่สำเร็จ → Strongly Connected

ตัวอย่างโค้ด

#include <iostream>
#include <list>
#include <vector>
using namespace std;

class Graph {
    int V;
    vector> adj;

    void dfs(int v, vector& visited) {
        visited[v] = true;
        for (int u : adj[v])
            if (!visited[u]) dfs(u, visited);
    }

public:
    Graph(int V) : V(V), adj(V) {}

    void addEdge(int u, int v) { adj[u].push_back(v); }

    Graph transpose() {
        Graph g(V);
        for (int u = 0; u < V; u++)
            for (int v : adj[u])
                g.adj[v].push_back(u);
        return g;
    }

    bool isStronglyConnected() {
        vector visited(V, false);
        dfs(0, visited);
        for (bool v : visited) if (!v) return false;

        Graph gt = transpose();
        fill(visited.begin(), visited.end(), false);
        gt.dfs(0, visited);
        for (bool v : visited) if (!v) return false;

        return true;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 0);
    g.addEdge(2, 4);
    g.addEdge(4, 2);

    cout << (g.isStronglyConnected() ? "Strongly Connected" : "Not Strongly Connected");
    return 0;
}

ผลลัพธ์

Strongly Connected

กราฟตัวอย่าง

0→1→2→3→0 (Cycle) และ 2↔4 (Two-way) → ทุกโหนดไปถึงกันได้

ความซับซ้อน

เวลา: O(V + E), พื้นที่: O(V + E)

อัลกอริทึมอื่น: Tarjan's SCC

หา Strongly Connected Components ทั้งหมดใน 1 Pass DFS (O(V+E)) หากมี SCC เพียง 1 ตัว = Strongly Connected