Kiểm tra đồ thị liên thông mạnh (Kosaraju DFS) C++

Đồ thị liên thông mạnh (Strongly Connected): Mọi cặp đỉnh u,v đều có đường đi u→v và v→u. Thuật toán Kosaraju dùng 2 lần DFS.

Các bước Kosaraju

1. DFS từ đỉnh bất kỳ (0). Nếu không thăm hết → false
2. Đảo ngược tất cả cạnh (transpose graph)
3. Đặt lại visited = false
4. DFS từ đỉnh 0 trên đồ thị đảo. Nếu không thăm hết → false
5. Cả 2 DFS đều thăm hết → Strongly Connected

Ví dụ minh họa

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

class Graph {
    int V;
    vector<int> *adj;
    void dfs(int v, vector<bool> &visited) {
        visited[v] = true;
        for (int u : adj[v])
            if (!visited[u]) dfs(u, visited);
    }
public:
    Graph(int V) : V(V) { adj = new vector<int>[V]; }
    ~Graph() { delete[] adj; }
    
    void addEdge(int u, int v) { adj[u].push_back(v); }
    
    Graph transpose() {
        Graph g(V);
        for (int v = 0; v < V; v++)
            for (int u : adj[v])
                g.adj[u].push_back(v);
        return g;
    }
    
    bool isStronglyConnected() {
        vector<bool> 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() ? "Lien thong manh" : "KHONG lien thong manh");
}

Kết quả

Lien thong manh