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
}