Amazon Online Assessment (OA) - DataCenter Critical Connection

Given a data center with n servers from 1 to n. To make the data center run, all servers must be connected, which means there exists at least one path between any pair of servers. Now we know there could be some critical connections that are broken, which brings down the whole data center.

You need to write a program to find out all these broken critical connections. A server connection is considered a critical connection, which, when removed, will make the whole data center disconnected.

Write a method to output all critical connections.

1public static List<List<Integer>> findCriticalConn(int serversNum, int connectionsNum, int[][] connections)

Input

The input consists of three arguments:

serversNum, the number of servers in the data center.

connectionsNum, the number of connections between the servers.

connections, a list of pairs representing the connections between two servers.

Output

Return a list of integer pairs representing the critical connections. Output an empty array if there are no critical connections.

Examples

Example 1:

Input:

serversNum = 4

connectionsNum = 4

connections = [[1, 2], [1, 3], [3, 2], [3, 4]]

Output: [[3,4]]

Explanation:

There is one critical connection:

1. Between servers 3 and 4 If the connection [3, 4] breaks, the network will be disconnected, as servers 3 and 4 cannot communicate with the rest of the network. The remaining three connections are not critical.

Try it yourself