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)