Critical Connections in a Network

Hard
0/120
profile
Contributed by
6 upvotes
Asked in companies
FacebookAmazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 4
1 2
1 3
2 3
2 4
3 2
1 2
2 3
Sample Output 1 :
2 4
1 2
2 3
Explanation of Sample Output 1 :
In test case 1, the graph is shown below.


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


In test case 2, the graph is shown below.


If we remove the connection between ‘3’ and ‘2’. Then ‘3’ will not be reachable from any other server. Similarly, if we remove the connection between ‘1’ and ‘2’. Then ‘1’ will not be reachable from any other server.
Sample Input 2 :
2
2 1
1 2
4 4
1 2
1 3
3 4
2 4
Sample Output 2 :
1 2
Explanation of Sample Output 2 :
In test case 1, the graph is shown below.


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

In test case 2, the graph is shown below.


No matter which connection we remove it is not possible to make some servers unable to reach some other server.
Hint

Remove every connection and check.

Approaches (2)
Brute Force

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 :

  1. 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.
Time Complexity

O( M * ( N + M ) ), where ‘N’ is the number of servers and ‘M’ denotes the number of connections.

 

We traverse through all connections and do DFS every time. The Time Complexity of DFS is O( N + M).

Hence the time complexity is O( M * ( N + M ) ).

Space Complexity

O( N * M ), where ‘N’ is the number of servers and ‘M’ denotes the number of connections.

 

We will use a visited array of size ‘N’ for DFS and there are ‘M’ such DFS calls.

Hence the space complexity is O( N * M ).

Code Solution
(100% EXP penalty)
Critical Connections in a Network
Full screen
Console