AntInLoop

Tarjan's Algorithm (SCCs, Bridges & Articulation Points) Code Implementations

Complete Tarjan's Algorithm (SCCs, Bridges & Articulation Points) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Tarjan's Algorithm (SCCs, Bridges & Articulation Points) Guide ยท Launch Interactive Visualizer

C++ Implementation

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

class TarjanAlgorithm {
private:
    static int time;
    
public:
    static std::vector<std::vector<int>> tarjanAlgorithm(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::unordered_set<int> onStack;
        std::unordered_map<int, int> low;
        std::unordered_map<int, int> disc;
        std::stack<int> stack;
        std::vector<std::vector<int>> sccs;
        time = 0;
        
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                dfs(graph, node, visited, onStack, low, disc, stack, sccs);
            }
        }
        
        return sccs;
    }
    
private:
    static void dfs(const std::unordered_map<int, std::vector<int>>& graph, int node,
                   std::unordered_set<int>& visited, std::unordered_set<int>& onStack,
                   std::unordered_map<int, int>& low, std::unordered_map<int, int>& disc,
                   std::stack<int>& stack, std::vector<std::vector<int>>& sccs) {
        visited.insert(node);
        onStack.insert(node);
        stack.push(node);
        
        disc[node] = time;
        low[node] = time;
        time++;
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    dfs(graph, neighbor, visited, onStack, low, disc, stack, sccs);
                    low[node] = std::min(low[node], low[neighbor]);
                } else if (onStack.find(neighbor) != onStack.end()) {
                    low[node] = std::min(low[node], disc[neighbor]);
                }
            }
        }
        
        // If this is a root node, pop the stack and form an SCC
        if (low[node] == disc[node]) {
            std::vector<int> scc;
            int w;
            do {
                w = stack.top();
                stack.pop();
                onStack.erase(w);
                scc.push_back(w);
            } while (w != node);
            sccs.push_back(scc);
        }
    }
    
public:
    // Tarjan's with additional information
    static std::unordered_map<std::string, std::vector<std::vector<int>>> tarjanWithInfo(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::unordered_set<int> onStack;
        std::unordered_map<int, int> low;
        std::unordered_map<int, int> disc;
        std::stack<int> stack;
        std::vector<std::vector<int>> sccs;
        std::vector<std::pair<int, int>> bridges;
        std::unordered_set<int> articulationPoints;
        time = 0;
        
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                dfsWithInfo(graph, node, -1, visited, onStack, low, disc, stack, sccs, bridges, articulationPoints);
            }
        }
        
        std::unordered_map<std::string, std::vector<std::vector<int>>> result;
        result["sccs"] = sccs;
        
        std::vector<std::vector<int>> bridgesVec;
        for (const auto& bridge : bridges) {
            bridgesVec.push_back({bridge.first, bridge.second});
        }
        result["bridges"] = bridgesVec;
        
        std::vector<std::vector<int>> articulationPointsVec;
        for (int point : articulationPoints) {
            articulationPointsVec.push_back({point});
        }
        result["articulationPoints"] = articulationPointsVec;
        
        return result;
    }
    
private:
    static void dfsWithInfo(const std::unordered_map<int, std::vector<int>>& graph, int node, int parent,
                           std::unordered_set<int>& visited, std::unordered_set<int>& onStack,
                           std::unordered_map<int, int>& low, std::unordered_map<int, int>& disc,
                           std::stack<int>& stack, std::vector<std::vector<int>>& sccs,
                           std::vector<std::pair<int, int>>& bridges, std::unordered_set<int>& articulationPoints) {
        visited.insert(node);
        onStack.insert(node);
        stack.push(node);
        
        disc[node] = time;
        low[node] = time;
        time++;
        
        int children = 0;
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    children++;
                    dfsWithInfo(graph, neighbor, node, visited, onStack, low, disc, stack, sccs, bridges, articulationPoints);
                    low[node] = std::min(low[node], low[neighbor]);
                    
                    // Check for bridges
                    if (low[neighbor] > disc[node]) {
                        bridges.push_back({node, neighbor});
                    }
                    
                    // Check for articulation points
                    if (parent == -1 && children > 1) {
                        articulationPoints.insert(node);
                    } else if (parent != -1 && low[neighbor] >= disc[node]) {
                        articulationPoints.insert(node);
                    }
                } else if (onStack.find(neighbor) != onStack.end()) {
                    low[node] = std::min(low[node], disc[neighbor]);
                }
            }
        }
        
        // If this is a root node, pop the stack and form an SCC
        if (low[node] == disc[node]) {
            std::vector<int> scc;
            int w;
            do {
                w = stack.top();
                stack.pop();
                onStack.erase(w);
                scc.push_back(w);
            } while (w != node);
            sccs.push_back(scc);
        }
    }
    
public:
    // Tarjan's for finding bridges
    static std::vector<std::pair<int, int>> tarjanBridges(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::unordered_map<int, int> low;
        std::unordered_map<int, int> disc;
        std::vector<std::pair<int, int>> bridges;
        time = 0;
        
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                dfsBridges(graph, node, -1, visited, low, disc, bridges);
            }
        }
        
        return bridges;
    }
    
private:
    static void dfsBridges(const std::unordered_map<int, std::vector<int>>& graph, int node, int parent,
                          std::unordered_set<int>& visited, std::unordered_map<int, int>& low,
                          std::unordered_map<int, int>& disc, std::vector<std::pair<int, int>>& bridges) {
        visited.insert(node);
        disc[node] = time;
        low[node] = time;
        time++;
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (neighbor == parent) continue;
                
                if (visited.find(neighbor) == visited.end()) {
                    dfsBridges(graph, neighbor, node, visited, low, disc, bridges);
                    low[node] = std::min(low[node], low[neighbor]);
                    
                    // Check for bridge
                    if (low[neighbor] > disc[node]) {
                        bridges.push_back({node, neighbor});
                    }
                } else {
                    low[node] = std::min(low[node], disc[neighbor]);
                }
            }
        }
    }
};

int TarjanAlgorithm::time = 0;

JAVA Implementation

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

public class TarjanAlgorithm {
    private static int time = 0;
    
    public static List<List<Integer>> tarjanAlgorithm(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> onStack = new HashSet<>();
        Map<Integer, Integer> low = new HashMap<>();
        Map<Integer, Integer> disc = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        List<List<Integer>> sccs = new ArrayList<>();
        time = 0;
        
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs(graph, node, visited, onStack, low, disc, stack, sccs);
            }
        }
        
        return sccs;
    }
    
    private static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited,
                           Set<Integer> onStack, Map<Integer, Integer> low, Map<Integer, Integer> disc,
                           Stack<Integer> stack, List<List<Integer>> sccs) {
        visited.add(node);
        onStack.add(node);
        stack.push(node);
        
        disc.put(node, time);
        low.put(node, time);
        time++;
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, onStack, low, disc, stack, sccs);
                low.put(node, Math.min(low.get(node), low.get(neighbor)));
            } else if (onStack.contains(neighbor)) {
                low.put(node, Math.min(low.get(node), disc.get(neighbor)));
            }
        }
        
        // If this is a root node, pop the stack and form an SCC
        if (low.get(node).equals(disc.get(node))) {
            List<Integer> scc = new ArrayList<>();
            int w;
            do {
                w = stack.pop();
                onStack.remove(w);
                scc.add(w);
            } while (w != node);
            sccs.add(scc);
        }
    }
    
    // Tarjan's with additional information
    public static Map<String, Object> tarjanWithInfo(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> onStack = new HashSet<>();
        Map<Integer, Integer> low = new HashMap<>();
        Map<Integer, Integer> disc = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        List<List<Integer>> sccs = new ArrayList<>();
        List<int[]> bridges = new ArrayList<>();
        Set<Integer> articulationPoints = new HashSet<>();
        time = 0;
        
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfsWithInfo(graph, node, -1, visited, onStack, low, disc, stack, sccs, bridges, articulationPoints);
            }
        }
        
        Map<String, Object> result = new HashMap<>();
        result.put("sccs", sccs);
        result.put("bridges", bridges);
        result.put("articulationPoints", new ArrayList<>(articulationPoints));
        return result;
    }
    
    private static void dfsWithInfo(Map<Integer, List<Integer>> graph, int node, int parent,
                                  Set<Integer> visited, Set<Integer> onStack, Map<Integer, Integer> low,
                                  Map<Integer, Integer> disc, Stack<Integer> stack, List<List<Integer>> sccs,
                                  List<int[]> bridges, Set<Integer> articulationPoints) {
        visited.add(node);
        onStack.add(node);
        stack.push(node);
        
        disc.put(node, time);
        low.put(node, time);
        time++;
        
        int children = 0;
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                children++;
                dfsWithInfo(graph, neighbor, node, visited, onStack, low, disc, stack, sccs, bridges, articulationPoints);
                low.put(node, Math.min(low.get(node), low.get(neighbor)));
                
                // Check for bridges
                if (low.get(neighbor) > disc.get(node)) {
                    bridges.add(new int[]{node, neighbor});
                }
                
                // Check for articulation points
                if (parent == -1 && children > 1) {
                    articulationPoints.add(node);
                } else if (parent != -1 && low.get(neighbor) >= disc.get(node)) {
                    articulationPoints.add(node);
                }
            } else if (onStack.contains(neighbor)) {
                low.put(node, Math.min(low.get(node), disc.get(neighbor)));
            }
        }
        
        // If this is a root node, pop the stack and form an SCC
        if (low.get(node).equals(disc.get(node))) {
            List<Integer> scc = new ArrayList<>();
            int w;
            do {
                w = stack.pop();
                onStack.remove(w);
                scc.add(w);
            } while (w != node);
            sccs.add(scc);
        }
    }
    
    // Tarjan's for finding bridges
    public static List<int[]> tarjanBridges(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Map<Integer, Integer> low = new HashMap<>();
        Map<Integer, Integer> disc = new HashMap<>();
        List<int[]> bridges = new ArrayList<>();
        time = 0;
        
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfsBridges(graph, node, -1, visited, low, disc, bridges);
            }
        }
        
        return bridges;
    }
    
    private static void dfsBridges(Map<Integer, List<Integer>> graph, int node, int parent,
                                 Set<Integer> visited, Map<Integer, Integer> low, Map<Integer, Integer> disc,
                                 List<int[]> bridges) {
        visited.add(node);
        disc.put(node, time);
        low.put(node, time);
        time++;
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (neighbor == parent) continue;
            
            if (!visited.contains(neighbor)) {
                dfsBridges(graph, neighbor, node, visited, low, disc, bridges);
                low.put(node, Math.min(low.get(node), low.get(neighbor)));
                
                // Check for bridge
                if (low.get(neighbor) > disc.get(node)) {
                    bridges.add(new int[]{node, neighbor});
                }
            } else {
                low.put(node, Math.min(low.get(node), disc.get(neighbor)));
            }
        }
    }
}

JAVASCRIPT Implementation

// Tarjan's Algorithm Implementation in JavaScript
function tarjanAlgorithm(graph) {
  const visited = new Set();
  const onStack = new Set();
  const low = new Map();
  const disc = new Map();
  const stack = [];
  const sccs = [];
  let time = 0;
  
  function dfs(node) {
    visited.add(node);
    onStack.add(node);
    stack.push(node);
    
    disc.set(node, time);
    low.set(node, time);
    time++;
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
        low.set(node, Math.min(low.get(node), low.get(neighbor)));
      } else if (onStack.has(neighbor)) {
        low.set(node, Math.min(low.get(node), disc.get(neighbor)));
      }
    }
    
    // If this is a root node, pop the stack and form an SCC
    if (low.get(node) === disc.get(node)) {
      const scc = [];
      let w;
      do {
        w = stack.pop();
        onStack.delete(w);
        scc.push(w);
      } while (w !== node);
      sccs.push(scc);
    }
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return sccs;
}

// Tarjan's with additional information
function tarjanWithInfo(graph) {
  const visited = new Set();
  const onStack = new Set();
  const low = new Map();
  const disc = new Map();
  const stack = [];
  const sccs = [];
  const bridges = [];
  const articulationPoints = new Set();
  let time = 0;
  
  function dfs(node, parent = null) {
    visited.add(node);
    onStack.add(node);
    stack.push(node);
    
    disc.set(node, time);
    low.set(node, time);
    time++;
    
    let children = 0;
    const neighbors = graph[node] || [];
    
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        children++;
        dfs(neighbor, node);
        low.set(node, Math.min(low.get(node), low.get(neighbor)));
        
        // Check for bridges
        if (low.get(neighbor) > disc.get(node)) {
          bridges.push([node, neighbor]);
        }
        
        // Check for articulation points
        if (parent === null && children > 1) {
          articulationPoints.add(node);
        } else if (parent !== null && low.get(neighbor) >= disc.get(node)) {
          articulationPoints.add(node);
        }
      } else if (onStack.has(neighbor)) {
        low.set(node, Math.min(low.get(node), disc.get(neighbor)));
      }
    }
    
    // If this is a root node, pop the stack and form an SCC
    if (low.get(node) === disc.get(node)) {
      const scc = [];
      let w;
      do {
        w = stack.pop();
        onStack.delete(w);
        scc.push(w);
      } while (w !== node);
      sccs.push(scc);
    }
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return {
    sccs,
    bridges,
    articulationPoints: Array.from(articulationPoints)
  };
}

// Tarjan's for finding bridges
function tarjanBridges(graph) {
  const visited = new Set();
  const low = new Map();
  const disc = new Map();
  const bridges = [];
  let time = 0;
  
  function dfs(node, parent = null) {
    visited.add(node);
    disc.set(node, time);
    low.set(node, time);
    time++;
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (neighbor === parent) continue;
      
      if (!visited.has(neighbor)) {
        dfs(neighbor, node);
        low.set(node, Math.min(low.get(node), low.get(neighbor)));
        
        // Check for bridge
        if (low.get(neighbor) > disc.get(node)) {
          bridges.push([node, neighbor]);
        }
      } else {
        low.set(node, Math.min(low.get(node), disc.get(neighbor)));
      }
    }
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return bridges;
}

// Tarjan's for finding articulation points
function tarjanArticulationPoints(graph) {
  const visited = new Set();
  const low = new Map();
  const disc = new Map();
  const articulationPoints = new Set();
  let time = 0;
  
  function dfs(node, parent = null) {
    visited.add(node);
    disc.set(node, time);
    low.set(node, time);
    time++;
    
    let children = 0;
    const neighbors = graph[node] || [];
    
    for (const neighbor of neighbors) {
      if (neighbor === parent) continue;
      
      if (!visited.has(neighbor)) {
        children++;
        dfs(neighbor, node);
        low.set(node, Math.min(low.get(node), low.get(neighbor)));
        
        // Check for articulation point
        if (parent === null && children > 1) {
          articulationPoints.add(node);
        } else if (parent !== null && low.get(neighbor) >= disc.get(node)) {
          articulationPoints.add(node);
        }
      } else {
        low.set(node, Math.min(low.get(node), disc.get(neighbor)));
      }
    }
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return Array.from(articulationPoints);
}

PYTHON Implementation

# Tarjan's Algorithm Implementation in Python
def tarjan_algorithm(graph):
    visited = set()
    on_stack = set()
    low = {}
    disc = {}
    stack = []
    sccs = []
    time = 0
    
    def dfs(node):
        nonlocal time
        visited.add(node)
        on_stack.add(node)
        stack.append(node)
        
        disc[node] = time
        low[node] = time
        time += 1
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs(neighbor)
                low[node] = min(low[node], low[neighbor])
            elif neighbor in on_stack:
                low[node] = min(low[node], disc[neighbor])
        
        # If this is a root node, pop the stack and form an SCC
        if low[node] == disc[node]:
            scc = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.append(w)
                if w == node:
                    break
            sccs.append(scc)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return sccs

# Tarjan's with additional information
def tarjan_with_info(graph):
    visited = set()
    on_stack = set()
    low = {}
    disc = {}
    stack = []
    sccs = []
    bridges = []
    articulation_points = set()
    time = 0
    
    def dfs(node, parent=None):
        nonlocal time
        visited.add(node)
        on_stack.add(node)
        stack.append(node)
        
        disc[node] = time
        low[node] = time
        time += 1
        
        children = 0
        neighbors = graph.get(node, [])
        
        for neighbor in neighbors:
            if neighbor not in visited:
                children += 1
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                
                # Check for bridges
                if low[neighbor] > disc[node]:
                    bridges.append([node, neighbor])
                
                # Check for articulation points
                if parent is None and children > 1:
                    articulation_points.add(node)
                elif parent is not None and low[neighbor] >= disc[node]:
                    articulation_points.add(node)
            elif neighbor in on_stack:
                low[node] = min(low[node], disc[neighbor])
        
        # If this is a root node, pop the stack and form an SCC
        if low[node] == disc[node]:
            scc = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.append(w)
                if w == node:
                    break
            sccs.append(scc)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return {
        'sccs': sccs,
        'bridges': bridges,
        'articulation_points': list(articulation_points)
    }

# Tarjan's for finding bridges
def tarjan_bridges(graph):
    visited = set()
    low = {}
    disc = {}
    bridges = []
    time = 0
    
    def dfs(node, parent=None):
        nonlocal time
        visited.add(node)
        disc[node] = time
        low[node] = time
        time += 1
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor == parent:
                continue
            
            if neighbor not in visited:
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                
                # Check for bridge
                if low[neighbor] > disc[node]:
                    bridges.append([node, neighbor])
            else:
                low[node] = min(low[node], disc[neighbor])
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return bridges

# Tarjan's for finding articulation points
def tarjan_articulation_points(graph):
    visited = set()
    low = {}
    disc = {}
    articulation_points = set()
    time = 0
    
    def dfs(node, parent=None):
        nonlocal time
        visited.add(node)
        disc[node] = time
        low[node] = time
        time += 1
        
        children = 0
        neighbors = graph.get(node, [])
        
        for neighbor in neighbors:
            if neighbor == parent:
                continue
            
            if neighbor not in visited:
                children += 1
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                
                # Check for articulation point
                if parent is None and children > 1:
                    articulation_points.add(node)
                elif parent is not None and low[neighbor] >= disc[node]:
                    articulation_points.add(node)
            else:
                low[node] = min(low[node], disc[neighbor])
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return list(articulation_points)

# Tarjan's for directed graph SCCs
def tarjan_directed_scc(graph):
    return tarjan_algorithm(graph)