LeetCode 1192: Critical Connections in a Network Solution

Master LeetCode problem 1192 (Critical Connections in a Network), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1192. Critical Connections in a Network

Hard

Depth-First Search Graph Biconnected Component

Problem Explanation

Explanation

To find critical connections in a network, we can use Tarjan's algorithm for finding strongly connected components in a graph. In this problem, we treat each server as a node in the graph and each connection as an edge. We can then identify the critical connections by finding the bridges in the graph.

The idea is to perform a depth-first search (DFS) starting from each node in the graph and keep track of the discovery time of each node and the lowest reachable node from that node. If the lowest reachable node from a node is greater than the discovery time of the current node, then the edge connecting them is a critical connection.

By using Tarjan's algorithm, we can efficiently find all critical connections in the network.

Time complexity: O(V + E) where V is the number of vertices (servers) and E is the number of edges (connections).
Space complexity: O(V + E) for storing the graph and the data structures used in Tarjan's algorithm.

Solution Code

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (List<Integer> connection : connections) {
            int from = connection.get(0);
            int to = connection.get(1);
            graph[from].add(to);
            graph[to].add(from);
        }
        
        int[] discovery = new int[n];
        int[] low = new int[n];
        Arrays.fill(discovery, -1);
        List<List<Integer>> bridges = new ArrayList<>();
        
        dfs(0, -1, 0, graph, discovery, low, bridges);
        
        for (List<Integer> bridge : bridges) {
            result.add(bridge);
        }
        
        return result;
    }
    
    private void dfs(int node, int parent, int time, List<Integer>[] graph, int[] discovery, int[] low, List<List<Integer>> bridges) {
        discovery[node] = time;
        low[node] = time;
        for (int neighbor : graph[node]) {
            if (neighbor == parent) {
                continue;
            }
            if (discovery[neighbor] == -1) {
                dfs(neighbor, node, time + 1, graph, discovery, low, bridges);
                low[node] = Math.min(low[node], low[neighbor]);
                if (low[neighbor] == discovery[neighbor]) {
                    bridges.add(Arrays.asList(node, neighbor));
                }
            } else {
                low[node] = Math.min(low[node], discovery[neighbor]);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1192 (Critical Connections in a Network)?

This page provides optimized solutions for LeetCode problem 1192 (Critical Connections in a Network) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1192 (Critical Connections in a Network)?

The time complexity for LeetCode 1192 (Critical Connections in a Network) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1192 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1192 in Java, C++, or Python.

Back to LeetCode Solutions