FastPrep
Problem · Graph

Supply Path Optimization

Learn this problem
● MediumInMobi logoInMobiFULLTIMEOA

Problem statement

An ad-tech supply network is represented by a connected undirected graph. Each node is a supply partner, each connection is a direct business relationship, and node 0 represents InMobi.

A connection is critical when removing that single edge increases the number of connected components. Find every critical connection.

Return each critical connection as a pair [u, v] with u < v. Sort the pairs lexicographically, first by u and then by v.

  • If the graph has at least one connection and every connection is critical, return [[-1]].
  • If no connection is critical, return an empty list.

Function

criticalConnections(n: int, connections: int[][]) → List<List<Integer>>

Examples

Example 1

n = 4connections = [[0,1],[1,2],[2,0],[1,3]]return = [[1,3]]

Removing [1, 3] disconnects node 3. Every other connection belongs to a cycle, so removing any one of them leaves the graph connected.

Constraints

  • 1 <= n <= 10^5
  • n - 1 <= connections.length <= 2 * 10^5
  • connections[i].length = 2
  • 0 <= connections[i][0], connections[i][1] < n
  • The graph is connected.

More InMobi problems

drafts saved locally
public List<List<Integer>> criticalConnections(int n, int[][] connections) {
    // write your code here
}
n4
connections[[0,1],[1,2],[2,0],[1,3]]
expected[[1,3]]
checking account