Algorithm for Finding Strongly Connected Components (SCCs)

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices such that every vertex is reachable from every other vertex in the set. Identifying SCCs is fundamental in graph theory, with applications in network analysis, program optimization, and dependency resolution.

---

🌍 Key Algorithms

Kosaraju’s Algorithm

• Runs in O(V + E) time.
• Steps:
  1. Perform DFS to compute finishing times of vertices.
  2. Reverse the graph.
  3. Perform DFS in order of decreasing finishing times to identify SCCs.

Tarjan’s Algorithm

• Also runs in O(V + E) time.
• Uses a single DFS with a stack and low-link values.
• More space-efficient since it avoids explicit graph reversal.

---

🛠️ Kosaraju’s Algorithm in C++

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

class Graph {
    int V;
    vector<vector<int>> adj;

    void DFSUtil(int v, vector<bool> &visited, vector<int> &component) {
        visited[v] = true;
        component.push_back(v);
        for (int u : adj[v]) {
            if (!visited[u]) DFSUtil(u, visited, component);
        }
    }

    void fillOrder(int v, vector<bool> &visited, stack<int> &Stack) {
        visited[v] = true;
        for (int u : adj[v]) {
            if (!visited[u]) fillOrder(u, visited, Stack);
        }
        Stack.push(v);
    }

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

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

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

    void printSCCs() {
        stack<int> Stack;
        vector<bool> visited(V, false);

        for (int i = 0; i < V; i++)
            if (!visited[i])
                fillOrder(i, visited, Stack);

        Graph gr = getTranspose();
        fill(visited.begin(), visited.end(), false);

        while (!Stack.empty()) {
            int v = Stack.top();
            Stack.pop();

            if (!visited[v]) {
                vector<int> component;
                gr.DFSUtil(v, visited, component);

                cout << "SCC: ";
                for (int node : component) cout << node << " ";
                cout << endl;
            }
        }
    }
};

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

    cout << "Strongly Connected Components:\n";
    g.printSCCs();

    return 0;
}

---

🐍 Kosaraju’s Algorithm in Python

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs_util(self, v, visited, component):
        visited[v] = True
        component.append(v)
        for u in self.graph[v]:
            if not visited[u]:
                self.dfs_util(u, visited, component)

    def fill_order(self, v, visited, stack):
        visited[v] = True
        for u in self.graph[v]:
            if not visited[u]:
                self.fill_order(u, visited, stack)
        stack.append(v)

    def get_transpose(self):
        g = Graph(self.V)
        for v in self.graph:
            for u in self.graph[v]:
                g.add_edge(u, v)
        return g

    def print_sccs(self):
        stack = []
        visited = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.fill_order(i, visited, stack)

        gr = self.get_transpose()
        visited = [False] * self.V

        while stack:
            v = stack.pop()
            if not visited[v]:
                component = []
                gr.dfs_util(v, visited, component)
                print("SCC:", component)

# Example usage
g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)

print("Strongly Connected Components:")
g.print_sccs()

---

📊 Comparison of C++ and Python Implementations

Feature	C++	Python
Syntax	Verbose, requires explicit memory handling	Concise, uses built-in data structures
Graph Representation	Vector of vectors	defaultdict(list)
Stack	std::stack	Python list
Performance	Faster, closer to hardware	Easier to write and debug

---

📖 Conclusion

Both Kosaraju’s and Tarjan’s algorithms efficiently find SCCs in O(V + E) time. The C++ version offers performance and control, while Python provides readability and simplicity. Mastering SCC algorithms is essential for solving problems in network analysis, compiler design, and dependency resolution.

Would you like me to also add Tarjan’s algorithm in both C++ and Python so you can compare single-pass vs. two-pass approaches?