Задача: 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 {
    private $graph;
    private $rank;
    private $connDict;
    
    function criticalConnections($n, $connections) {
        $this->formGraph($n, $connections);
        $this->dfs(0, 0);
        
        $result = [];
        foreach ($this->connDict as $conn => $_) {
            $result[] = explode(",", $conn);
        }
        return $result;
    }
    
    private function dfs($node, $discoveryRank) {
        if (isset($this->rank[$node])) {
            return $this->rank[$node];
        }
        
        $this->rank[$node] = $discoveryRank;
        $minRank = $discoveryRank + 1;
        
        foreach ($this->graph[$node] as $neighbor) {
            if (isset($this->rank[$neighbor]) && $this->rank[$neighbor] == $discoveryRank - 1) {
                continue;
            }
            
            $recursiveRank = $this->dfs($neighbor, $discoveryRank + 1);
            
            if ($recursiveRank <= $discoveryRank) {
                unset($this->connDict[implode(",", [min($node, $neighbor), max($node, $neighbor)])]);
            }
            
            $minRank = min($minRank, $recursiveRank);
        }
        
        return $minRank;
    }
    
    private function formGraph($n, $connections) {
        $this->graph = array_fill(0, $n, []);
        $this->rank = array_fill(0, $n, null);
        $this->connDict = [];
        
        foreach ($connections as $edge) {
            list($u, $v) = $edge;
            $this->graph[$u][] = $v;
            $this->graph[$v][] = $u;
            $this->connDict[implode(",", [min($u, $v), max($u, $v)])] = true;
        }
    }
}

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