Critical Connections in a Network - Practice Coding Problems

Critical Connections in a Network - Problem

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi.

Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Input & Output

Example 1 — Simple Network

$ Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

› Output: [[1,3]]

💡 Note: Servers 0, 1, 2 form a cycle, so any connection between them can be removed without disconnecting. However, connection [1,3] is critical - removing it would isolate server 3.

Example 2 — Linear Chain

$ Input: n = 3, connections = [[0,1],[1,2]]

› Output: [[0,1],[1,2]]

💡 Note: This is a linear chain where both connections are critical. Removing either [0,1] or [1,2] would disconnect the network into separate components.

Example 3 — Single Connection

$ Input: n = 2, connections = [[0,1]]

› Output: [[0,1]]

💡 Note: With only two servers and one connection, that connection is critical since removing it would completely disconnect the servers.

Constraints

1 ≤ n ≤ 10⁵
n - 1 ≤ connections.length ≤ 10⁵
0 ≤ ai, bi ≤ n - 1
ai ≠ bi
There are no repeated connections.

Visualization

Tap to expand

Understanding the Visualization

Input Network

Servers connected by bidirectional links

Identify Bridges

Find connections critical for connectivity

Output Result

Return all critical connections

Key Takeaway

🎯 Key Insight: Critical connections are graph bridges - edges whose removal disconnects the network into separate components

Asked in

G Google 45 a Amazon 38 f Facebook 29 M Microsoft 25

The key insight is that critical connections are bridges in graph theory - edges whose removal increases the number of connected components. Tarjan's algorithm efficiently finds all bridges using DFS with discovery time and low-link values in O(V + E) time. Best approach is DFS with Tarjan's algorithm: Time O(V + E), Space O(V + E).

Common Approaches

Approach	Time	Space	Notes
✓ Tarjan's Algorithm - DFS with Low-Link Values	O(V + E)	O(V + E)	Find bridges using DFS with discovery time and low-link values
Brute Force - Remove Each Edge	O(E × (V + E))	O(V + E)	Remove each connection and check if graph becomes disconnected

Tarjan's Algorithm - DFS with Low-Link Values — Algorithm Steps

Initialize discovery time and low-link arrays
Run DFS from any unvisited node
For each edge (u,v), if low[v] > disc[u], it's a bridge
Update low-link values during backtracking

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from node 0, assign discovery times

Update Low-Links

Calculate lowest reachable discovery time

Find Bridges

Edge (u,v) is bridge if low[v] > disc[u]

Code -

solution.c — C

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

#define MAX_N 100000
#define MAX_EDGES 100000

int graph[MAX_N][MAX_N];
int graphCount[MAX_N];
bool visited[MAX_N];
int disc[MAX_N];
int low[MAX_N];
int parent[MAX_N];
int bridges[MAX_EDGES][2];
int bridgeCount;
int timer;

int min(int a, int b) {
    return a < b ? a : b;
}

void dfs(int u) {
    visited[u] = true;
    disc[u] = low[u] = timer++;
    
    for (int i = 0; i < graphCount[u]; i++) {
        int v = graph[u][i];
        if (!visited[v]) {
            parent[v] = u;
            dfs(v);
            
            low[u] = min(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] = min(low[u], disc[v]);
        }
    }
}

int solution(int n, int connections[][2], int connectionsSize) {
    memset(graphCount, 0, sizeof(graphCount));
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; i++) parent[i] = -1;
    bridgeCount = 0;
    timer = 0;
    
    for (int i = 0; i < connectionsSize; i++) {
        int u = connections[i][0], v = connections[i][1];
        graph[u][graphCount[u]++] = v;
        graph[v][graphCount[v]++] = u;
    }
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    
    return bridgeCount;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[100000];
    scanf(" %[^\n]", line);
    
    int connections[MAX_EDGES][2];
    int connectionsSize = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            connections[connectionsSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            connections[connectionsSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            connectionsSize++;
        } else {
            ptr++;
        }
    }
    
    int resultSize = solution(n, connections, connectionsSize);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("[%d,%d]", bridges[i][0], bridges[i][1]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Single DFS traversal visits each vertex and edge exactly once

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list storage plus DFS recursion stack depth O(V)

✓ Linear Space

125.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Tarjan's Algorithm - DFS with Low-Link Values — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler