AntInLoop

Kosaraju's Algorithm (Strongly Connected Components) Code Implementations

Complete Kosaraju's Algorithm (Strongly Connected Components) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Kosaraju's Algorithm (Strongly Connected Components) Guide ยท Launch Interactive Visualizer

C++ Implementation

// Kosaraju's Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

class KosarajuAlgorithm {
public:
    static std::vector<std::vector<int>> kosarajuAlgorithm(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::vector<int> order;
        std::vector<std::vector<int>> sccs;
        
        // First DFS to get topological order
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                dfs1(graph, node, visited, order);
            }
        }
        
        // Create transpose graph
        auto transposeGraph = createTransposeGraph(graph);
        
        // Reset visited set
        visited.clear();
        
        // Second pass: find SCCs
        for (int i = order.size() - 1; i >= 0; i--) {
            int node = order[i];
            if (visited.find(node) == visited.end()) {
                std::vector<int> scc;
                dfs2(transposeGraph, node, visited, scc);
                sccs.push_back(scc);
            }
        }
        
        return sccs;
    }
    
private:
    static void dfs1(const std::unordered_map<int, std::vector<int>>& graph, int node,
                    std::unordered_set<int>& visited, std::vector<int>& order) {
        visited.insert(node);
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    dfs1(graph, neighbor, visited, order);
                }
            }
        }
        
        order.push_back(node);
    }
    
    static void dfs2(const std::unordered_map<int, std::vector<int>>& graph, int node,
                    std::unordered_set<int>& visited, std::vector<int>& scc) {
        visited.insert(node);
        scc.push_back(node);
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    dfs2(graph, neighbor, visited, scc);
                }
            }
        }
    }
    
    static std::unordered_map<int, std::vector<int>> createTransposeGraph(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_map<int, std::vector<int>> transposeGraph;
        
        for (const auto& [node, neighbors] : graph) {
            if (transposeGraph.find(node) == transposeGraph.end()) {
                transposeGraph[node] = std::vector<int>();
            }
            
            for (int neighbor : neighbors) {
                if (transposeGraph.find(neighbor) == transposeGraph.end()) {
                    transposeGraph[neighbor] = std::vector<int>();
                }
                transposeGraph[neighbor].push_back(node);
            }
        }
        
        return transposeGraph;
    }
    
public:
    // Kosaraju's with additional information
    static std::unordered_map<std::string, std::vector<std::vector<int>>> kosarajuWithInfo(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::vector<int> order;
        std::vector<std::vector<int>> sccs;
        std::unordered_map<int, int> sccMap;
        
        // First DFS to get topological order
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                dfs1(graph, node, visited, order);
            }
        }
        
        // Create transpose graph
        auto transposeGraph = createTransposeGraph(graph);
        
        // Reset visited set
        visited.clear();
        
        // Second pass: find SCCs
        int sccIndex = 0;
        for (int i = order.size() - 1; i >= 0; i--) {
            int node = order[i];
            if (visited.find(node) == visited.end()) {
                std::vector<int> scc;
                dfs2WithMap(transposeGraph, node, visited, scc, sccMap, sccIndex);
                sccs.push_back(scc);
                sccIndex++;
            }
        }
        
        std::unordered_map<std::string, std::vector<std::vector<int>>> result;
        result["sccs"] = sccs;
        
        // Convert sccMap to vector format for consistency
        std::vector<std::vector<int>> sccMapVec;
        for (const auto& [node, sccIndex] : sccMap) {
            sccMapVec.push_back({node, sccIndex});
        }
        result["sccMap"] = sccMapVec;
        
        return result;
    }
    
private:
    static void dfs2WithMap(const std::unordered_map<int, std::vector<int>>& graph, int node,
                           std::unordered_set<int>& visited, std::vector<int>& scc,
                           std::unordered_map<int, int>& sccMap, int sccIndex) {
        visited.insert(node);
        scc.push_back(node);
        sccMap[node] = sccIndex;
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    dfs2WithMap(graph, neighbor, visited, scc, sccMap, sccIndex);
                }
            }
        }
    }
    
public:
    // Kosaraju's for checking if graph is strongly connected
    static bool kosarajuIsStronglyConnected(const std::unordered_map<int, std::vector<int>>& graph) {
        auto sccs = kosarajuAlgorithm(graph);
        return sccs.size() == 1;
    }
    
    // Kosaraju's for finding condensation graph
    static std::unordered_map<std::string, std::vector<std::vector<int>>> kosarajuCondensation(const std::unordered_map<int, std::vector<int>>& graph) {
        auto result = kosarajuWithInfo(graph);
        auto sccs = result["sccs"];
        
        // Create condensation graph
        std::unordered_map<int, std::unordered_set<int>> condensationGraph;
        std::unordered_set<std::string> sccEdges;
        
        for (const auto& [node, neighbors] : graph) {
            int nodeSCC = -1;
            int neighborSCC = -1;
            
            // Find SCC indices (simplified)
            for (size_t i = 0; i < sccs.size(); i++) {
                for (int sccNode : sccs[i]) {
                    if (sccNode == node) nodeSCC = i;
                }
            }
            
            for (int neighbor : neighbors) {
                for (size_t i = 0; i < sccs.size(); i++) {
                    for (int sccNode : sccs[i]) {
                        if (sccNode == neighbor) neighborSCC = i;
                    }
                }
                
                if (nodeSCC != neighborSCC && nodeSCC != -1 && neighborSCC != -1) {
                    condensationGraph[nodeSCC].insert(neighborSCC);
                    sccEdges.insert(std::to_string(nodeSCC) + "->" + std::to_string(neighborSCC));
                }
            }
        }
        
        std::unordered_map<std::string, std::vector<std::vector<int>>> condensationResult;
        condensationResult["sccs"] = sccs;
        
        // Convert condensation graph to vector format
        std::vector<std::vector<int>> condensationVec;
        for (const auto& [scc, neighbors] : condensationGraph) {
            std::vector<int> sccNeighbors;
            sccNeighbors.push_back(scc);
            for (int neighbor : neighbors) {
                sccNeighbors.push_back(neighbor);
            }
            condensationVec.push_back(sccNeighbors);
        }
        condensationResult["condensationGraph"] = condensationVec;
        
        return condensationResult;
    }
};

JAVA Implementation

// Kosaraju's Algorithm Implementation in Java
import java.util.*;

public class KosarajuAlgorithm {
    public static List<List<Integer>> kosarajuAlgorithm(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> order = new ArrayList<>();
        List<List<Integer>> sccs = new ArrayList<>();
        
        // First DFS to get topological order
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs1(graph, node, visited, order);
            }
        }
        
        // Create transpose graph
        Map<Integer, List<Integer>> transposeGraph = createTransposeGraph(graph);
        
        // Reset visited set
        visited.clear();
        
        // Second pass: find SCCs
        for (int i = order.size() - 1; i >= 0; i--) {
            int node = order.get(i);
            if (!visited.contains(node)) {
                List<Integer> scc = new ArrayList<>();
                dfs2(transposeGraph, node, visited, scc);
                sccs.add(scc);
            }
        }
        
        return sccs;
    }
    
    private static void dfs1(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, List<Integer> order) {
        visited.add(node);
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfs1(graph, neighbor, visited, order);
            }
        }
        
        order.add(node);
    }
    
    private static void dfs2(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, List<Integer> scc) {
        visited.add(node);
        scc.add(node);
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfs2(graph, neighbor, visited, scc);
            }
        }
    }
    
    private static Map<Integer, List<Integer>> createTransposeGraph(Map<Integer, List<Integer>> graph) {
        Map<Integer, List<Integer>> transposeGraph = new HashMap<>();
        
        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            int node = entry.getKey();
            List<Integer> neighbors = entry.getValue();
            
            if (!transposeGraph.containsKey(node)) {
                transposeGraph.put(node, new ArrayList<>());
            }
            
            for (int neighbor : neighbors) {
                if (!transposeGraph.containsKey(neighbor)) {
                    transposeGraph.put(neighbor, new ArrayList<>());
                }
                transposeGraph.get(neighbor).add(node);
            }
        }
        
        return transposeGraph;
    }
    
    // Kosaraju's with additional information
    public static Map<String, Object> kosarajuWithInfo(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> order = new ArrayList<>();
        List<List<Integer>> sccs = new ArrayList<>();
        Map<Integer, Integer> sccMap = new HashMap<>();
        
        // First DFS to get topological order
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs1(graph, node, visited, order);
            }
        }
        
        // Create transpose graph
        Map<Integer, List<Integer>> transposeGraph = createTransposeGraph(graph);
        
        // Reset visited set
        visited.clear();
        
        // Second pass: find SCCs
        int sccIndex = 0;
        for (int i = order.size() - 1; i >= 0; i--) {
            int node = order.get(i);
            if (!visited.contains(node)) {
                List<Integer> scc = new ArrayList<>();
                dfs2WithMap(transposeGraph, node, visited, scc, sccMap, sccIndex);
                sccs.add(scc);
                sccIndex++;
            }
        }
        
        Map<String, Object> result = new HashMap<>();
        result.put("sccs", sccs);
        result.put("sccMap", sccMap);
        result.put("order", order);
        result.put("transposeGraph", transposeGraph);
        return result;
    }
    
    private static void dfs2WithMap(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited,
                                   List<Integer> scc, Map<Integer, Integer> sccMap, int sccIndex) {
        visited.add(node);
        scc.add(node);
        sccMap.put(node, sccIndex);
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfs2WithMap(graph, neighbor, visited, scc, sccMap, sccIndex);
            }
        }
    }
    
    // Kosaraju's for checking if graph is strongly connected
    public static boolean kosarajuIsStronglyConnected(Map<Integer, List<Integer>> graph) {
        List<List<Integer>> sccs = kosarajuAlgorithm(graph);
        return sccs.size() == 1;
    }
    
    // Kosaraju's for finding condensation graph
    public static Map<String, Object> kosarajuCondensation(Map<Integer, List<Integer>> graph) {
        Map<String, Object> result = kosarajuWithInfo(graph);
        @SuppressWarnings("unchecked")
        List<List<Integer>> sccs = (List<List<Integer>>) result.get("sccs");
        @SuppressWarnings("unchecked")
        Map<Integer, Integer> sccMap = (Map<Integer, Integer>) result.get("sccMap");
        
        // Create condensation graph
        Map<Integer, Set<Integer>> condensationGraph = new HashMap<>();
        Set<String> sccEdges = new HashSet<>();
        
        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            int node = entry.getKey();
            List<Integer> neighbors = entry.getValue();
            int nodeSCC = sccMap.get(node);
            
            if (!condensationGraph.containsKey(nodeSCC)) {
                condensationGraph.put(nodeSCC, new HashSet<>());
            }
            
            for (int neighbor : neighbors) {
                int neighborSCC = sccMap.get(neighbor);
                if (nodeSCC != neighborSCC) {
                    condensationGraph.get(nodeSCC).add(neighborSCC);
                    sccEdges.add(nodeSCC + "->" + neighborSCC);
                }
            }
        }
        
        Map<String, Object> condensationResult = new HashMap<>();
        condensationResult.put("sccs", sccs);
        condensationResult.put("condensationGraph", condensationGraph);
        condensationResult.put("sccEdges", new ArrayList<>(sccEdges));
        return condensationResult;
    }
}

JAVASCRIPT Implementation

// Kosaraju's Algorithm Implementation in JavaScript
function kosarajuAlgorithm(graph) {
  const visited = new Set();
  const order = [];
  const sccs = [];
  
  // First DFS to get topological order
  function dfs1(node) {
    visited.add(node);
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs1(neighbor);
      }
    }
    
    order.push(node);
  }
  
  // Second DFS on transpose graph
  function dfs2(node, scc) {
    visited.add(node);
    scc.push(node);
    
    const neighbors = transposeGraph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs2(neighbor, scc);
      }
    }
  }
  
  // Create transpose graph
  const transposeGraph = {};
  for (const node in graph) {
    if (!transposeGraph[node]) {
      transposeGraph[node] = [];
    }
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!transposeGraph[neighbor]) {
        transposeGraph[neighbor] = [];
      }
      transposeGraph[neighbor].push(node);
    }
  }
  
  // First pass: topological sort
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs1(node);
    }
  }
  
  // Reset visited set
  visited.clear();
  
  // Second pass: find SCCs
  for (let i = order.length - 1; i >= 0; i--) {
    const node = order[i];
    if (!visited.has(node)) {
      const scc = [];
      dfs2(node, scc);
      sccs.push(scc);
    }
  }
  
  return sccs;
}

// Kosaraju's with additional information
function kosarajuWithInfo(graph) {
  const visited = new Set();
  const order = [];
  const sccs = [];
  const sccMap = new Map(); // Maps node to its SCC index
  
  // First DFS to get topological order
  function dfs1(node) {
    visited.add(node);
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs1(neighbor);
      }
    }
    
    order.push(node);
  }
  
  // Second DFS on transpose graph
  function dfs2(node, scc, sccIndex) {
    visited.add(node);
    scc.push(node);
    sccMap.set(node, sccIndex);
    
    const neighbors = transposeGraph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs2(neighbor, scc, sccIndex);
      }
    }
  }
  
  // Create transpose graph
  const transposeGraph = {};
  for (const node in graph) {
    if (!transposeGraph[node]) {
      transposeGraph[node] = [];
    }
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!transposeGraph[neighbor]) {
        transposeGraph[neighbor] = [];
      }
      transposeGraph[neighbor].push(node);
    }
  }
  
  // First pass: topological sort
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs1(node);
    }
  }
  
  // Reset visited set
  visited.clear();
  
  // Second pass: find SCCs
  let sccIndex = 0;
  for (let i = order.length - 1; i >= 0; i--) {
    const node = order[i];
    if (!visited.has(node)) {
      const scc = [];
      dfs2(node, scc, sccIndex);
      sccs.push(scc);
      sccIndex++;
    }
  }
  
  return {
    sccs,
    sccMap,
    order,
    transposeGraph
  };
}

// Kosaraju's for finding condensation graph
function kosarajuCondensation(graph) {
  const result = kosarajuWithInfo(graph);
  const { sccs, sccMap } = result;
  
  // Create condensation graph
  const condensationGraph = {};
  const sccEdges = new Set();
  
  for (const node in graph) {
    const nodeSCC = sccMap.get(node);
    if (!condensationGraph[nodeSCC]) {
      condensationGraph[nodeSCC] = new Set();
    }
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      const neighborSCC = sccMap.get(neighbor);
      if (nodeSCC !== neighborSCC) {
        condensationGraph[nodeSCC].add(neighborSCC);
                        sccEdges.add(nodeSCC + "->" + neighborSCC);
      }
    }
  }
  
  return {
    sccs,
    condensationGraph,
    sccEdges: Array.from(sccEdges)
  };
}

// Kosaraju's for checking if graph is strongly connected
function kosarajuIsStronglyConnected(graph) {
  const sccs = kosarajuAlgorithm(graph);
  return sccs.length === 1;
}

// Kosaraju's for finding source and sink components
function kosarajuSourceSink(graph) {
  const result = kosarajuWithInfo(graph);
  const { sccs, sccMap, condensationGraph } = result;
  
  const sources = [];
  const sinks = [];
  
  for (let i = 0; i < sccs.length; i++) {
    const inDegree = new Set();
    const outDegree = new Set();
    
    for (const node of sccs[i]) {
      const neighbors = graph[node] || [];
      for (const neighbor of neighbors) {
        const neighborSCC = sccMap.get(neighbor);
        if (i !== neighborSCC) {
          outDegree.add(neighborSCC);
        }
      }
    }
    
    for (const node of sccs[i]) {
      for (const otherSCC in condensationGraph) {
        if (condensationGraph[otherSCC] && condensationGraph[otherSCC].has(i)) {
          inDegree.add(parseInt(otherSCC));
        }
      }
    }
    
    if (inDegree.size === 0) {
      sources.push(i);
    }
    if (outDegree.size === 0) {
      sinks.push(i);
    }
  }
  
  return {
    sccs,
    sources,
    sinks
  };
}

PYTHON Implementation

# Kosaraju's Algorithm Implementation in Python
def kosaraju_algorithm(graph):
    visited = set()
    order = []
    sccs = []
    
    # First DFS to get topological order
    def dfs1(node):
        visited.add(node)
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs1(neighbor)
        
        order.append(node)
    
    # Second DFS on transpose graph
    def dfs2(node, scc):
        visited.add(node)
        scc.append(node)
        
        neighbors = transpose_graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs2(neighbor, scc)
    
    # Create transpose graph
    transpose_graph = {}
    for node in graph:
        if node not in transpose_graph:
            transpose_graph[node] = []
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in transpose_graph:
                transpose_graph[neighbor] = []
            transpose_graph[neighbor].append(node)
    
    # First pass: topological sort
    for node in graph:
        if node not in visited:
            dfs1(node)
    
    # Reset visited set
    visited.clear()
    
    # Second pass: find SCCs
    for i in range(len(order) - 1, -1, -1):
        node = order[i]
        if node not in visited:
            scc = []
            dfs2(node, scc)
            sccs.append(scc)
    
    return sccs

# Kosaraju's with additional information
def kosaraju_with_info(graph):
    visited = set()
    order = []
    sccs = []
    scc_map = {}  # Maps node to its SCC index
    
    # First DFS to get topological order
    def dfs1(node):
        visited.add(node)
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs1(neighbor)
        
        order.append(node)
    
    # Second DFS on transpose graph
    def dfs2(node, scc, scc_index):
        visited.add(node)
        scc.append(node)
        scc_map[node] = scc_index
        
        neighbors = transpose_graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs2(neighbor, scc, scc_index)
    
    # Create transpose graph
    transpose_graph = {}
    for node in graph:
        if node not in transpose_graph:
            transpose_graph[node] = []
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in transpose_graph:
                transpose_graph[neighbor] = []
            transpose_graph[neighbor].append(node)
    
    # First pass: topological sort
    for node in graph:
        if node not in visited:
            dfs1(node)
    
    # Reset visited set
    visited.clear()
    
    # Second pass: find SCCs
    scc_index = 0
    for i in range(len(order) - 1, -1, -1):
        node = order[i]
        if node not in visited:
            scc = []
            dfs2(node, scc, scc_index)
            sccs.append(scc)
            scc_index += 1
    
    return {
        'sccs': sccs,
        'scc_map': scc_map,
        'order': order,
        'transpose_graph': transpose_graph
    }

# Kosaraju's for finding condensation graph
def kosaraju_condensation(graph):
    result = kosaraju_with_info(graph)
    sccs = result['sccs']
    scc_map = result['scc_map']
    
    # Create condensation graph
    condensation_graph = {}
    scc_edges = set()
    
    for node in graph:
        node_scc = scc_map[node]
        if node_scc not in condensation_graph:
            condensation_graph[node_scc] = set()
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            neighbor_scc = scc_map[neighbor]
            if node_scc != neighbor_scc:
                condensation_graph[node_scc].add(neighbor_scc)
                scc_edges.add(f"{node_scc}->{neighbor_scc}")
    
    return {
        'sccs': sccs,
        'condensation_graph': condensation_graph,
        'scc_edges': list(scc_edges)
    }

# Kosaraju's for checking if graph is strongly connected
def kosaraju_is_strongly_connected(graph):
    sccs = kosaraju_algorithm(graph)
    return len(sccs) == 1

# Kosaraju's for finding source and sink components
def kosaraju_source_sink(graph):
    result = kosaraju_with_info(graph)
    sccs = result['sccs']
    scc_map = result['scc_map']
    
    # Create condensation graph for analysis
    condensation_result = kosaraju_condensation(graph)
    condensation_graph = condensation_result['condensation_graph']
    
    sources = []
    sinks = []
    
    for i in range(len(sccs)):
        in_degree = set()
        out_degree = set()
        
        for node in sccs[i]:
            neighbors = graph.get(node, [])
            for neighbor in neighbors:
                neighbor_scc = scc_map[neighbor]
                if i != neighbor_scc:
                    out_degree.add(neighbor_scc)
        
        for node in sccs[i]:
            for other_scc in condensation_graph:
                if other_scc in condensation_graph and i in condensation_graph[other_scc]:
                    in_degree.add(other_scc)
        
        if len(in_degree) == 0:
            sources.append(i)
        if len(out_degree) == 0:
            sinks.append(i)
    
    return {
        'sccs': sccs,
        'sources': sources,
        'sinks': sinks
    }