Bridges in Graph
Strongly Connected Components & Bridges DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding Critical Connections (Bridges) in an Undirected Graph, Graph, Undirected Graph, Edge, Depth-First Search, Time Complexity, Space Complexity, Connected Components, Adjacency List, Recursion, Algorithm, Arrays, graph representation, graph algorithms, tarjan's algorithm, backtracking, dfs, Bridges in Graph (Tarjan's Algorithm).
Problem Statement: There are n servers numbered from 0 to n 1 connected by undirected server to server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. 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 servers. Return all critical connections in the network in any order. Input Specification: The first line contains an integer N, the number of servers. The second line contains a list of connections, where each connection is a pair of integers [ai, bi] representing a connection between servers ai and bi. Output Specification: Return a list of lists of integers, where each inner list represents a critical connection [u, v]. The order of connections and the order of servers within a connection does not matter. Constraints: (Constraints were not provided in the original content.) Sample Input 1: N = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Sample Output 1: [[1, 3]] Explanation 1: The edge [1, 3] is the critical edge because if it is removed, the graph will be divided into 2 components.