Задача: 1192. Critical Connections in a Network
Сложность: hard

Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть.

Критическое соединение — это соединение, удаление которого сделает невозможным достижение некоторыми серверами других серверов.
Верните все критические соединения в сети в любом порядке.

Пример:

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

👨‍💻 Алгоритм:

1⃣Построение графа и инициализация:
Постройте граф в виде списка смежности и создайте словарь для хранения соединений.
Инициализируйте ранги для узлов.

2⃣Поиск в глубину (DFS):
Реализуйте функцию dfs для обхода графа.
Обновите ранги узлов и определите минимальный ранг для текущего узла.
Проверьте, можно ли удалить текущее соединение, и обновите минимальный ранг.

3⃣Поиск критических соединений:
После завершения обхода DFS преобразуйте оставшиеся соединения в список и верните его.

😎 Решение:

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;
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний