Critical Connections in a Network — LeetCode

[Prapattimynk]

Critical Connections in a Network — LeetCode #1192 (Hard)

Problem Link

There are n servers numbered from 0 to n - 1, connected by undirected "server-to-server" connections, where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i.
Any server can reach other servers directly or indirectly through the network.

A **critical connection** is a connection that, if removed, will make it impossible for some servers to reach others.

Return all critical connections in the network in any order.

Example:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Algorithm:

1. Build the Graph:
   Use an adjacency list to store connections and a dictionary to mark edges as existing.
2. DFS with Rank Tracking:
   - Use DFS to assign discovery ranks to nodes.
   - The rank represents the time a node is visited.
   - If a connection leads to a back edge, it is **not** critical.
3. Identify Critical Edges:
   - If the lowest reachable rank from a neighbor is greater than the current node's discovery rank, the edge is critical.
   - Store remaining edges as critical connections.

Solution in JavaScript

class Solution {
    constructor() {
        this.graph = {};
        this.rank = {};
        this.connDict = {};
    }

    criticalConnections(n, connections) {
        this.formGraph(n, connections);
        this.dfs(0, 0);
        let result = [];
        for (let key in this.connDict) {
            result.push(key.split(',').map(Number));
        }
        return result;
    }

    dfs(node, discoveryRank) {
        if (this.rank[node] !== undefined) {
            return this.rank[node];
        }

        this.rank[node] = discoveryRank;
        let minRank = discoveryRank + 1;

        for (let neighbor of this.graph[node]) {
            if (this.rank[neighbor] !== undefined && this.rank[neighbor] === discoveryRank - 1) {
                continue;
            }

            let recursiveRank = this.dfs(neighbor, discoveryRank + 1);

            if (recursiveRank <= discoveryRank) {
                delete this.connDict[[Math.min(node, neighbor), Math.max(node, neighbor)]];
            }

            minRank = Math.min(minRank, recursiveRank);
        }

        return minRank;
    }

    formGraph(n, connections) {
        for (let i = 0; i < n; i++) {
            this.graph[i] = [];
            this.rank[i] = undefined;
        }

        for (let [u, v] of connections) {
            this.graph[u].push(v);
            this.graph[v].push(u);
            this.connDict[[Math.min(u, v), Math.max(u, v)]] = true;
        }
    }
}

Complexity Analysis:
- **Time Complexity**: O(N + E) where N = number of servers, E = number of connections.
- **Space Complexity**: O(N + E) for graph storage.

Resources:
Take the Knowledge Base — More JavaScript & algorithm practice problems.