#1192

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Critical Connections in a Network

Find critical connections in a network of servers, ensuring efficient traversal using depth-first search and Tarjan's algorithm.

depth first search graph biconnected component

Problem Statement

You are given a network of n servers, numbered from 0 to n - 1, and a list of undirected server-to-server connections. Each connection is represented as an array [ai, bi], where ai and bi are the server indices connected by the edge. The task is to find and return all critical connections in the network, i.e., connections whose removal would increase the number of disconnected components in the graph.

A critical connection is defined as an edge that, if removed, would disconnect some part of the graph. These are the edges whose failure would break the network's connectivity. You need to return these critical connections in any order. Consider using depth-first search and Tarjan's algorithm to find these edges efficiently.

Examples

Example 1

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: [[1,3]]

[[3,1]] is also accepted.

Example 2

Input: n = 2, connections = [[0,1]]

Output: [[0,1]]

Example details omitted.

Constraints

2 <= n <= 105
n - 1 <= connections.length <= 105
0 <= ai, bi <= n - 1
ai != bi
There are no repeated connections.

Solution Approach

Graph Representation and DFS Setup

Start by representing the network as a graph using an adjacency list. Initialize DFS arrays to track discovery times, low values, and parent-child relationships in the DFS tree. These arrays are crucial for identifying critical connections by exploring the graph recursively.

Tarjan’s Algorithm for Finding Bridges

Apply Tarjan's algorithm, which uses DFS to find bridges in the graph. A bridge is a critical connection if no back edges exist from the connected component to any earlier node in the DFS tree. During DFS, update the discovery and low time values to detect these conditions.

Edge Identification and Output

During the DFS traversal, check if the current edge satisfies the condition of being a critical connection. If the low value of the adjacent node is greater than the discovery time of the current node, the edge is critical. Collect and return these edges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n + m) where n is the number of servers and m is the number of connections, as we traverse each node and edge once during the DFS. The space complexity is O(n + m) due to the storage requirements for the graph representation and DFS state arrays.

What Interviewers Usually Probe

Look for the candidate's ability to implement depth-first search and handle graph traversal efficiently.
Assess understanding of Tarjan's algorithm and its application to finding critical connections.
Evaluate how the candidate handles edge cases, such as small or sparse graphs, and ensures correctness.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly track low and discovery times in the DFS process can lead to incorrect identification of critical connections.
Ignoring edge cases, such as when there are very few connections or the network is already disconnected.
Not considering the constraint that the network has no repeated connections, which affects how the graph is processed.

Follow-up variants

Finding all bridges in a directed graph with similar conditions.
Optimizing for very large graphs with hundreds of thousands of nodes and edges.
Implementing an iterative version of Tarjan's algorithm to avoid recursion depth issues in large graphs.

FAQ

What is Tarjan's algorithm, and how does it help find critical connections?

Tarjan's algorithm is a depth-first search-based approach that helps identify bridges in a graph, which are critical connections that, if removed, would disconnect parts of the graph.

What is the time complexity of finding critical connections in a network?

The time complexity is O(n + m), where n is the number of nodes (servers) and m is the number of edges (connections), due to the graph traversal using DFS.

How do critical connections relate to biconnected components in graph theory?

Critical connections are edges that, if removed, would increase the number of biconnected components in the graph, as they connect separate components of the network.

Can this approach be used for directed graphs?

Yes, with modifications, Tarjan's algorithm can be adapted to find critical connections in directed graphs, though the logic for back edges would differ.

What happens if there are no critical connections in the network?

If there are no critical connections, the network is fully connected in such a way that no single edge can disconnect any part of the graph.

terminal

Solution

Solution 1: Tarjan Algorithm

The "critical connections" in this problem can be considered as "bridges".

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Solution:
    def criticalConnections(
        self, n: int, connections: List[List[int]]
    ) -> List[List[int]]:
        def tarjan(a: int, fa: int):
            nonlocal now
            now += 1
            dfn[a] = low[a] = now
            for b in g[a]:
                if b == fa:
                    continue
                if not dfn[b]:
                    tarjan(b, a)
                    low[a] = min(low[a], low[b])
                    if low[b] > dfn[a]:
                        ans.append([a, b])
                else:
                    low[a] = min(low[a], dfn[b])

        g = [[] for _ in range(n)]
        for a, b in connections:
            g[a].append(b)
            g[b].append(a)

        dfn = [0] * n
        low = [0] * n
        now = 0
        ans = []
        tarjan(0, -1)
        return ans

Continue Practicing

#1203 sort items by groups respecting dependencies #1319 number of operations to make network connected #1042 flower planting with no adjacent