Critical Connections In A Network - Leetcode Solution

Problem Statement:

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

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

Return all critical connections in the network in any order.

Example:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted.

Approach:

This problem can be solved using Tarjan's algorithm.

We will perform the following steps:

1. Convert the input into adjacency list format, as each server can have multiple connections.

2. Mark all the vertices as unvisited.

3. For each vertex, perform a DFS traversal and update the low-link value of each vertex. low-link value is defined as the smallest vertex index that can be reached from the current vertex in the DFS traversal.

We will maintain a list called ‘discovery time’ which stores the discovery time of each vertex visited during the DFS traversal.

Another list called ‘low-link-value’ will be used to store the low-link value of each vertex in the graph.

We will also maintain a list to store the critical connections found so far.

4. We will repeat step 3 until the root node has two distinct children in the DFS tree.

5. Now we will traverse the graph again, and for each edge [u, v], if low-link[v] > discovery_time[u], then [u, v] is a critical connection.

Algorithm:

function criticalConnections(n, connections): Initialize all the variables (adj_list, visited, discovery_time, low, parent, critical_connections)

for each vertex in the graph:
    perform a DFS to calculate the low-link value of each vertex

traverse the graph again:
    if low[v] > discovery_time[u]:
        add the edge (u, v) in the critical_connections list

return critical_connections

Code:

Time Complexity: O(N+E) where N is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(N+E) for adjacency list and O(N) for visited, discovery_time, low, and parent list, and O(N) for the result list.

1