Last Updated: 27 Jan, 2022

Critical Connections in a Network

Hard

Asked in companies

Solve now

Problem statement

There are ‘N’ servers numbered from ‘1’ to ‘N’ connected by undirected server-to-server connections forming a network.

You are given a matrix ‘EDGES’ storing the information about the connections, where each row, ‘EDGES[i]’ contains two integers ‘U’ and ‘V’, which implies that there is an undirected server-to-server connection between ‘U’ and ‘V’.

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. If there are no critical connections return empty matrix.

For Example:

For the given graph

If we remove the connection between ‘2’ and ‘4’. Then ‘4’ will not be reachable from any other server.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘M’, denoting the number of servers and number of connections respectively.

The following ‘M’ lines contain two integers ‘U’ and ‘V’ denoting there is an undirected server-to-server connection between server ‘U’ and server ‘V’.

Output Format :

For each test case, print all the critical connections in any order on separate lines.

Note :

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 ≤ T ≤ 10
2 ≤ N ≤ 100
N - 1 ≤ M ≤ 100
1 ≤ U, V ≤ N

Time limit: 1 sec

Solve now

Approaches

01 Approach

A simple approach is to one by one remove every connection and see if removal of this connection causes some servers to be unreachable from others. We can do this using DFS.

The steps are as follows :

for every connection (u, v), do the following:
- Remove (u, v) from the network
- Check if the network is disconnected. We can do this by starting DFS from server ‘1’ and checking if all servers are visited. If all servers are not visited then this connection (u, v) is a critical connection.
- Add (u, v) back to the network.

Solve now

02 Approach

We are basically given an undirected graph and we need to find all the bridges in it. A bridge is defined as an edge that, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all bridges in the given graph.

Pick an arbitrary vertex of the graph root and run DFS from it. Note the following fact (which is easy to prove):

Let's say we are in the DFS, looking through the edges starting from vertex u. The current edge (u, v) is a bridge if and only if none of the vertices v and its descendants in the DFS traversal tree has a back-edge to vertex u or any of its ancestors. Indeed, this condition means that there is no other way from u to v except for edge (u, v).

Now we have to learn to check this fact for each vertex efficiently. We'll use "time of entry into node" computed by the depth-first search.

So, let ‘tIn[u]’ denote entry time for node u. We introduce an array ‘low’ which will let us check the fact for each vertex u. ‘low[u]’ is the minimum of ‘tIn[u]’, the entry times ‘tIn[p]’ for each node p that is connected to node u via a back-edge (u, p) and the values of ‘low[v]’ for each vertex v which is a direct descendant of u in the DFS tree:

low[u] = min{ tIn[u],

tIn[p] (for all p for which (u, p) is back-edge),

low[v](for all v for which (u, v) is a tree edge) }

Now, there is a back edge from vertex u or one of its descendants to one of its ancestors if and only if vertex u has a child v for which low[v] ≤ in[u]. If low[v] = tIn[u], the back edge comes directly to u, otherwise it comes to one of the ancestors of u.

Thus, the current edge (u, v) in the DFS tree is a bridge if and only if low[v] >tIn[u].

The steps are as follows :

Declare ‘timer’ variable and initialize it to 0.
Declare ‘visited’ array and initialize all values to false.
Declare ‘tIn’ and ‘low’ arrays and initialize all values to ‘-1’.
Declare ‘bridges’ array to store all bridges in the graph.
for every node N:
- if N is not visited:
  - dfs(N)
dfs(u, p):
- Mark ‘u’ as visited.
- tIn[u] = low[u] = timer
- Increment timer i.e. timer++
- for every adjacent v of u:
  - If v is parent just continue
  - If v is already visited, means back-edge, then low[u] = min(low[u], tIn[v])
  - Else call dfs(v, u) and update low[u] = min(low[u], low[v]) also check if low[v] > tIn[u], then push this edge (u, v) to ‘bridges’ array.

Solve now