Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Given a network of servers where each server is connected to every other server directly or indirectly through the bidirectional connections in the network, find all the critical connections.

A connection in a connected network is said to be critical if removing it disconnects the network.

**Example One**

Input:

*n* = 5

*connections* = [

[0, 1],

[0, 2],

[0, 4],

[1, 2],

[1, 3]

]

Output: [

[0, 4],

[1, 3]

]

**Example Two**

Input:

*n* = 4

*connections* = [

[0, 1],

[0, 2],

[0, 3],

[1, 2],

[2, 3]

]

Output: [

[-1, -1]

]

Removal of any connection will not disconnect the network.

- Return [[-1,-1]] when there is no critical connection in the network.

Constraints:

- 1 <= number of servers <= 10^5
- 0 <= number of connections <= 10^5
- Servers are numbered from 0 to (number of servers - 1).
- There are no self-loops and multiple edges.

We have provided two solutions.

We will start with a brute force approach first, later we will present an optimal solution.

Consider the servers as vertices and connections as edges of an undirected graph.

Remove all edges of the graph one at a time, and see if the removal of the edge creates a disconnected graph. The solution has the following steps:

For every edge *e* in the graph,

a. Remove *e* from the graph

b. See if the graph remains connected (by using BFS or DFS)

c. Add *e* back to the graph

**Time complexity:**

O(number_of_connections * (number_of_servers + number_of_connections))

To create adjacency list = O(number_of_connections).

To apply DFS/BFS for *number_of_connections* times algorithm = O(number_of_connections * (number_of_servers + number_of_connections)).

**Auxiliary Space Used:**

O(number_of_servers + number_of_connections).

Memory used for adjacency list = O(number_of_servers + number_of_connections).

Memory used for marking nodes in BFS = O(number_of_servers).

Memory used for recursion call stack (only for DFS) = O(number_of_servers).

**Space Complexity:**

O(number_of_servers + number_of_connections).

Memory used for input = O(number_of_connections).

Memory used for output = O(number_of_connections).

Auxiliary space = O(number_of_servers + number_of_connections).

Total space complexity = O(number_of_servers + number_of_connections).

The concept of critical connection here is the famous concept in graph theory called “Bridges”. Question is to find out all the bridges in the given graph.

The idea is to use DFS (Depth First Search). In the DFS tree, any tree edge (*u*, *v*) where *v* is the parent node of *u*, is a bridge if none of the descendants of *u *has a back-edge to any of the ancestors of *v*. This means there is no way from *u* to *v* except for the edge (*u*, *v*). If a back-edge is found, this means there exists another path from *u* to *v, *and node *u* and *v* will still be connected if edge(*u*, *v*) is removed. Also, the back-edge can’t be a bridge because the edge(*u*, *v*) will keep the graph connected if the back-edge is removed.

We maintain an array that stores the discovery times of each vertex computed by DFS. Also, we store the earliest visited vertex (the vertex with minimum discovery time) that can be reached from subtree rooted at *v*. So we maintain an additional array *lowest_time* where *lowest_time[v] *is the minimum of:

1. *discovery_time[v]*

2. *discovery_time[p]*,* *for all *p *for which (*v, p*) is a back-edge

3. *lowest_time[u]*, for all *u *for which (*v, u*) is a tree edge, here *u* belongs to the subtree of *v*.

Now, for an edge (*u, v*), there is a back edge from vertex *u *or from one of its descendants to *v* or one of its ancestors if *lowest_time[u] <= discovery_time[v]. *Thus, if *lowest_time[u] > discovery_time[v]*, edge (*u*, *v*) is a bridge.

For better understanding, please have a look at the solution.

**Time Complexity:**

O(number_of_servers + number_of_connections)

To create adjacency list = O(number_of_connections).

DFS algorithm = O(number_of_servers + number_of_connections).

**Auxiliary Space Used:**

O(number_of_servers + number_of_connections).

Memory used for adjacency list = O(number_of_servers + number_of_connections).

Memory used for visited, discovery time, lowest time array = O(number_of_servers).

**Space Complexity:**

O(number_of_servers + number_of_connections).

Memory used for input = O(number_of_connections).

Memory used for output = O(number_of_connections).

Auxiliary space = O(number_of_servers + number_of_connections).

Total space complexity = O(number_of_servers + number_of_connections).

Note: Input and Output will already be taken care of.