ProgramGuru

Bridges in Graph using Tarjan's Algorithm

Problem and examples

You are given a network of n servers numbered from 0 to n - 1 connected by undirected server-to-server connections, where each connection is represented as [a, b].

A critical connection is a connection that, if removed, will disconnect the network — making some servers unreachable from others.

Return all such critical connections in any order.

Note: In this problem, servers are treated as nodes of a graph, and connections as undirected edges. The goal is to find all bridges in the graph using Tarjan's Algorithm.

n Connections Output Description
4 [[0,1],[1,2],[2,0],[1,3]] [[1,3]] Removing edge 1-3 disconnects node 3
5 [[0,1],[1,2],[2,3],[3,4],[4,2]] [[0,1]] Only 0-1 is a bridge; others are in a cycle
2 [[0,1]] [[0,1]] Single connection is always a bridge
3 [[0,1],[1,2],[2,0]] [] Fully connected triangle — no bridges
0 [] [] Empty graph, no edges or bridges

Explore Find Bridges in Graph Using Tarjan's Algorithm

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given a network of servers (nodes) connected by undirected edges. Each connection is a two-way link. Our goal is to find all critical connections, also known as bridges.

A bridge is an edge that, if removed, would increase the number of connected components in the graph. In simple terms, removing that edge disconnects part of the network. This is a classic graph problem, and we can solve it efficiently using Tarjan’s Algorithm, which is based on Depth-First Search (DFS).

Step-by-Step Solution with Example

step 1: Represent the Graph

We first build an adjacency list from the input list of connections. This allows us to efficiently explore all neighbors of a node during DFS.

step 2: Setup Required Structures

We initialize:

  • visited[]: to keep track of visited nodes
  • tin[]: stores the discovery time (insertion time) for each node
  • low[]: the lowest discovery time reachable from that node or its subtree
  • timer: a global counter to assign discovery times
  • result[]: a list to store all bridges found

step 3: Run DFS from Any Node

We begin DFS traversal from an unvisited node. During DFS:

  • We mark the node as visited and assign its tin and low values using the global timer.
  • For each neighbor:
    • If the neighbor is the parent (the node we came from), we skip it.
    • If the neighbor is already visited, it means a back edge exists. We update the current node’s low value using the neighbor’s tin.
    • If the neighbor is unvisited, we recursively apply DFS on it. After returning, we update the current node’s low value based on the neighbor’s low. If low[neighbor] > tin[current], then [current, neighbor] is a bridge.

step 4: Example Walkthrough

Let's consider this input:

n = 5  
connections = [[0,1],[1,2],[2,0],[1,3],[3,4]]

This forms the following graph:

  • A cycle: 0–1–2–0
  • Two edges: 1–3 and 3–4 (which are not part of any cycle)

Running Tarjan's algorithm:

  • DFS visits nodes and assigns timestamps
  • When we backtrack, we find that removing 1–3 or 3–4 would increase the number of components

Output: [[3, 4], [1, 3]]

Edge Cases

  • Disconnected Graph: If the graph has multiple disconnected parts, run DFS for each unvisited node.
  • No Bridges: If the graph is fully connected with cycles (like a complete graph), then no bridge will be found.
  • Single Node: No connections to check, return an empty list.
  • Tree Structure: Every edge in a tree is a bridge since removing any edge disconnects the graph.

Finally

Tarjan’s Algorithm is an elegant and efficient solution to detect bridges in a graph. By tracking the discovery time and the lowest reachable ancestor for each node, we can find edges that, if removed, disconnect the graph. The algorithm runs in O(V + E) time and is highly suitable for large graphs.

Understanding the idea of back edges and how they affect the low value is key to mastering this approach. With step-by-step DFS and careful updates, even beginners can grasp the intuition behind finding critical connections in a network.

  1. Initialize graph as an adjacency list.
  2. Create arrays: tin[], low[] and visited[] of size n.
  3. Set a timer = 0.
  4. For each unvisited node, run DFS:
    1. Mark node as visited, set tin[node] = low[node] = timer++.
    2. For each neighbor:
      1. If it is the parent, continue.
      2. If not visited, recurse and update low[node].
      3. If low[neighbor] > tin[node], then [node, neighbor] is a bridge.
      4. If already visited, update low[node] = min(low[node], tin[neighbor]).

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

// Structure for adjacency list node
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// Structure for adjacency list
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// Graph structure
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// Function to create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of V vertices
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an undirected edge
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Global variables for Tarjan's Algorithm
int timeCounter = 0;

void bridgeUtil(Graph* graph, int u, int visited[], int disc[], int low[], int parent[], int bridges[][2], int* bridgeCount) {
    visited[u] = 1;
    disc[u] = low[u] = ++timeCounter;

    AdjListNode* temp = graph->array[u].head;
    while (temp != NULL) {
        int v = temp->dest;
        if (!visited[v]) {
            parent[v] = u;
            bridgeUtil(graph, v, visited, disc, low, parent, bridges, bridgeCount);

            low[u] = (low[u] < low[v]) ? low[u] : low[v];

            if (low[v] > disc[u]) {
                bridges[*bridgeCount][0] = u;
                bridges[*bridgeCount][1] = v;
                (*bridgeCount)++;
            }
        } else if (v != parent[u]) {
            low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
        }
        temp = temp->next;
    }
}

void findBridges(Graph* graph) {
    int V = graph->V;
    int visited[V], disc[V], low[V], parent[V];
    for (int i = 0; i < V; i++) {
        visited[i] = 0;
        parent[i] = -1;
    }

    int bridges[V * V][2]; // Max possible bridges
    int bridgeCount = 0;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            bridgeUtil(graph, i, visited, disc, low, parent, bridges, &bridgeCount);
        }
    }

    printf("Critical connections (bridges):\n");
    for (int i = 0; i < bridgeCount; i++) {
        printf("%d - %d\n", bridges[i][0], bridges[i][1]);
    }
}

int main() {
    int n = 4;
    Graph* graph = createGraph(n);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 1, 3);

    findBridges(graph);
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

class Graph {
    int V;
    vector<vector<int>> adj;
    int time = 0;

    void bridgeUtil(int u, vector<bool>& visited, vector<int>& disc, vector<int>& low, vector<int>& parent, vector<pair<int,int>>& bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time;

        for (int v : adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                bridgeUtil(v, visited, disc, low, parent, bridges);
                low[u] = min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    bridges.push_back({u, v});
                }
            } else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

public:
    Graph(int V) : V(V) {
        adj.resize(V);
    }

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

    void findBridges() {
        vector<bool> visited(V, false);
        vector<int> disc(V, -1);
        vector<int> low(V, -1);
        vector<int> parent(V, -1);
        vector<pair<int,int>> bridges;

        for (int i = 0; i < V; ++i) {
            if (!visited[i]) {
                bridgeUtil(i, visited, disc, low, parent, bridges);
            }
        }

        cout << "Critical connections (bridges):" << endl;
        for (auto& bridge : bridges) {
            cout << bridge.first << " - " << bridge.second << endl;
        }
    }
};

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

    graph.findBridges();

    return 0;
}

Python implementation

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def critical_connections(n, connections):
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    time = 0
    visited = [False] * n
    disc = [-1] * n
    low = [-1] * n
    bridges = []

    def dfs(u, parent):
        nonlocal time
        visited[u] = True
        disc[u] = low[u] = time
        time += 1

        for v in graph[u]:
            if v == parent:
                continue
            if not visited[v]:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if not visited[i]:
            dfs(i, -1)

    return bridges

if __name__ == "__main__":
    n = 4
    connections = [[0,1],[1,2],[2,0],[1,3]]
    print("Critical connections (bridges):", critical_connections(n, connections))

Java implementation

import java.util.*;

public class CriticalConnections {
    private int time = 0;
    private List<List<Integer>> graph;
    private int[] disc, low, parent;
    private boolean[] visited;
    private List<List<Integer>> bridges;

    public CriticalConnections(int n) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        disc = new int[n];
        low = new int[n];
        parent = new int[n];
        visited = new boolean[n];
        Arrays.fill(parent, -1);
        bridges = new ArrayList<>();
    }

    public void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    private void dfs(int u) {
        visited[u] = true;
        disc[u] = low[u] = ++time;

        for (int v : graph.get(u)) {
            if (!visited[v]) {
                parent[v] = u;
                dfs(v);
                low[u] = Math.min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    bridges.add(Arrays.asList(u, v));
                }
            } else if (v != parent[u]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

    public List<List<Integer>> findBridges() {
        for (int i = 0; i < graph.size(); i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return bridges;
    }

    public static void main(String[] args) {
        CriticalConnections cc = new CriticalConnections(4);
        cc.addEdge(0, 1);
        cc.addEdge(1, 2);
        cc.addEdge(2, 0);
        cc.addEdge(1, 3);

        List<List<Integer>> result = cc.findBridges();
        System.out.println("Critical connections (bridges):");
        for (List<Integer> edge : result) {
            System.out.println(edge.get(0) + " - " + edge.get(1));
        }
    }
}

JavaScript implementation

function criticalConnections(n, connections) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of connections) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const tin = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const visited = new Array(n).fill(false);
  const bridges = [];
  let timer = 0;

  function dfs(node, parent) {
    visited[node] = true;
    tin[node] = low[node] = timer++;

    for (const neighbor of graph[node]) {
      if (neighbor === parent) continue;

      if (!visited[neighbor]) {
        dfs(neighbor, node);
        low[node] = Math.min(low[node], low[neighbor]);

        if (low[neighbor] > tin[node]) {
          bridges.push([node, neighbor]);
        }
      } else {
        low[node] = Math.min(low[node], tin[neighbor]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i, -1);
    }
  }

  return bridges;
}

console.log("Critical connections (bridges):", criticalConnections(4, [[0,1],[1,2],[2,0],[1,3]]));

Go implementation

package main

import (
    "fmt"
)

type Graph struct {
    V    int
    adj  [][]int
    time int
}

func NewGraph(V int) *Graph {
    g := &Graph{
        V:   V,
        adj: make([][]int, V),
    }
    return g
}

func (g *Graph) AddEdge(u, v int) {
    g.adj[u] = append(g.adj[u], v)
    g.adj[v] = append(g.adj[v], u)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func (g *Graph) bridgeUtil(u int, visited []bool, disc []int, low []int, parent []int, bridges *[][2]int) {
    visited[u] = true
    g.time++
    disc[u] = g.time
    low[u] = g.time

    for _, v := range g.adj[u] {
        if !visited[v] {
            parent[v] = u
            g.bridgeUtil(v, visited, disc, low, parent, bridges)
            low[u] = min(low[u], low[v])

            if low[v] > disc[u] {
                *bridges = append(*bridges, [2]int{u, v})
            }
        } else if v != parent[u] {
            low[u] = min(low[u], disc[v])
        }
    }
}

func (g *Graph) FindBridges() [][2]int {
    visited := make([]bool, g.V)
    disc := make([]int, g.V)
    low := make([]int, g.V)
    parent := make([]int, g.V)
    for i := 0; i < g.V; i++ {
        parent[i] = -1
    }

    var bridges [][2]int

    for i := 0; i < g.V; i++ {
        if !visited[i] {
            g.bridgeUtil(i, visited, disc, low, parent, &bridges)
        }
    }

    return bridges
}

func main() {
    g := NewGraph(4)
    g.AddEdge(0, 1)
    g.AddEdge(1, 2)
    g.AddEdge(2, 0)
    g.AddEdge(1, 3)

    bridges := g.FindBridges()
    fmt.Println("Critical connections (bridges):")
    for _, bridge := range bridges {
        fmt.Println(bridge[0], "-", bridge[1])
    }
}

Rust implementation

use std::collections::VecDeque;

struct Graph {
    adj: Vec<Vec<usize>>,
    time: usize,
}

impl Graph {
    fn new(v: usize) -> Self {
        Self {
            adj: vec![Vec::new(); v],
            time: 0,
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.adj[u].push(v);
        self.adj[v].push(u);
    }

    fn bridge_util(&mut self, u: usize, visited: &mut Vec<bool>, disc: &mut Vec<usize>, low: &mut Vec<usize>, parent: &mut Vec<Option<usize>>, bridges: &mut Vec<(usize, usize)>) {
        visited[u] = true;
        self.time += 1;
        disc[u] = self.time;
        low[u] = self.time;

        for &v in &self.adj[u] {
            if !visited[v] {
                parent[v] = Some(u);
                self.bridge_util(v, visited, disc, low, parent, bridges);
                low[u] = low[u].min(low[v]);

                if low[v] > disc[u] {
                    bridges.push((u, v));
                }
            } else if Some(v) != parent[u] {
                low[u] = low[u].min(disc[v]);
            }
        }
    }

    fn find_bridges(&mut self) -> Vec<(usize, usize)> {
        let v = self.adj.len();
        let mut visited = vec![false; v];
        let mut disc = vec![0; v];
        let mut low = vec![0; v];
        let mut parent = vec![None; v];
        let mut bridges = Vec::new();

        for i in 0..v {
            if !visited[i] {
                self.bridge_util(i, &mut visited, &mut disc, &mut low, &mut parent, &mut bridges);
            }
        }

        bridges
    }
}

fn main() {
    let mut graph = Graph::new(4);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(2, 0);
    graph.add_edge(1, 3);

    let bridges = graph.find_bridges();
    println!("Critical connections (bridges):");
    for (u, v) in bridges {
        println!("{} - {}", u, v);
    }
}

Kotlin implementation

fun main() {
    val n = 4
    val graph = Array(n) { mutableListOf<Int>() }

    fun addEdge(u: Int, v: Int) {
        graph[u].add(v)
        graph[v].add(u)
    }

    addEdge(0, 1)
    addEdge(1, 2)
    addEdge(2, 0)
    addEdge(1, 3)

    val time = IntArray(n) { -1 }
    val low = IntArray(n) { -1 }
    val visited = BooleanArray(n) { false }
    val bridges = mutableListOf<Pair<Int, Int>>()
    var timer = 0

    fun dfs(u: Int, parent: Int) {
        visited[u] = true
        time[u] = timer
        low[u] = timer
        timer++

        for (v in graph[u]) {
            if (v == parent) continue
            if (!visited[v]) {
                dfs(v, u)
                low[u] = minOf(low[u], low[v])
                if (low[v] > time[u]) {
                    bridges.add(Pair(u, v))
                }
            } else {
                low[u] = minOf(low[u], time[v])
            }
        }
    }

    for (i in 0 until n) {
        if (!visited[i]) {
            dfs(i, -1)
        }
    }

    println("Critical connections (bridges):")
    for ((u, v) in bridges) {
        println("$u - $v")
    }
}

Swift implementation

import Foundation

class Graph {
    let V: Int
    var adj: [[Int]]
    var time = 0

    init(_ V: Int) {
        self.V = V
        adj = Array(repeating: [], count: V)
    }

    func addEdge(_ u: Int, _ v: Int) {
        adj[u].append(v)
        adj[v].append(u)
    }

    func bridgeUtil(_ u: Int, _ visited: inout [Bool], _ disc: inout [Int], _ low: inout [Int], _ parent: inout [Int], _ bridges: inout [(Int, Int)]) {
        visited[u] = true
        time += 1
        disc[u] = time
        low[u] = time

        for v in adj[u] {
            if !visited[v] {
                parent[v] = u
                bridgeUtil(v, &visited, &disc, &low, &parent, &bridges)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u] {
                    bridges.append((u, v))
                }
            } else if v != parent[u] {
                low[u] = min(low[u], disc[v])
            }
        }
    }

    func findBridges() -> [(Int, Int)] {
        var visited = Array(repeating: false, count: V)
        var disc = Array(repeating: 0, count: V)
        var low = Array(repeating: 0, count: V)
        var parent = Array(repeating: -1, count: V)
        var bridges = [(Int, Int)]()

        for i in 0 ..< V {
            if !visited[i] {
                bridgeUtil(i, &visited, &disc, &low, &parent, &bridges)
            }
        }

        return bridges
    }
}

let graph = Graph(4)
graph.addEdge(0, 1)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(1, 3)

let bridges = graph.findBridges()
print("Critical connections (bridges):")
for (u, v) in bridges {
    print("\(u) - \(v)")
}

TypeScript implementation

function criticalConnections(n: number, connections: number[][]): number[][] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of connections) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const tin: number[] = new Array(n).fill(-1);
  const low: number[] = new Array(n).fill(-1);
  const visited: boolean[] = new Array(n).fill(false);
  const bridges: number[][] = [];
  let timer = 0;

  function dfs(node: number, parent: number) {
    visited[node] = true;
    tin[node] = low[node] = timer++;

    for (const neighbor of graph[node]) {
      if (neighbor === parent) continue;

      if (!visited[neighbor]) {
        dfs(neighbor, node);
        low[node] = Math.min(low[node], low[neighbor]);

        if (low[neighbor] > tin[node]) {
          bridges.push([node, neighbor]);
        }
      } else {
        low[node] = Math.min(low[node], tin[neighbor]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i, -1);
    }
  }

  return bridges;
}

console.log("Critical connections (bridges):", criticalConnections(4, [[0,1],[1,2],[2,0],[1,3]]));