← Static tasks

1192. Critical Connections in a Network

leetcode hard

#csharp#graph#hard#hash-table#leetcode#math#recursion#search

Task

Сложение:

Существует 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.

C# solution

matched/original
public class Solution {
    private Dictionary<int, List<int>> graph;
    private Dictionary<int, int?> rank;
    private Dictionary<(int, int), bool> connDict;
    
    public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections) {
        formGraph(n, connections);
        dfs(0, 0);
        
        var result = new List<IList<int>>();
        foreach (var conn in connDict.Keys) {
            result.Add(new List<int> { conn.Item1, conn.Item2 });
        }
        return result;
    }
    
    private int dfs(int node, int discoveryRank) {
        if (rank[node] != null) {
            return rank[node].Value;
        }
        
        rank[node] = discoveryRank;
        int minRank = discoveryRank + 1;
        
        foreach (var neighbor in graph[node]) {
            if (rank[neighbor] != null && rank[neighbor] == discoveryRank - 1) {
                continue;
            }
            
            int recursiveRank = dfs(neighbor, discoveryRank + 1);
            
            if (recursiveRank <= discoveryRank) {
                connDict.Remove((Math.Min(node, neighbor), Math.Max(node, neighbor)));
            }
            
            minRank = Math.Min(minRank, recursiveRank);
        }
        
        return minRank;
    }
    
    private void formGraph(int n, IList<IList<int>> connections) {
        graph = new Dictionary<int, List<int>>();
        rank = new Dictionary<int, int?>();
        connDict = new Dictionary<(int, int), bool>();
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
            rank[i] = null;
        }
        
        foreach (var edge in connections) {
            int u = edge[0], v = edge[1];
            graph[u].Add(v);
            graph[v].Add(u);
            connDict[(Math.Min(u, v), Math.Max(u, v))] = true;
        }
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<int, List<int>> graph;
    private unordered_map<int, int?> rank;
    private unordered_map<(int, int), bool> connDict;
    
    public IList<vector<int>> CriticalConnections(int n, IList<vector<int>> connections) {
        formGraph(n, connections);
        dfs(0, 0);
        
        var result = new List<vector<int>>();
        foreach (var conn in connDict.Keys) {
            result.push_back(new List<int> { conn.Item1, conn.Item2 });
        }
        return result;
    }
    
    private int dfs(int node, int discoveryRank) {
        if (rank[node] != null) {
            return rank[node].Value;
        }
        
        rank[node] = discoveryRank;
        int minRank = discoveryRank + 1;
        
        foreach (var neighbor in graph[node]) {
            if (rank[neighbor] != null && rank[neighbor] == discoveryRank - 1) {
                continue;
            }
            
            int recursiveRank = dfs(neighbor, discoveryRank + 1);
            
            if (recursiveRank <= discoveryRank) {
                connDict.Remove((min(node, neighbor), max(node, neighbor)));
            }
            
            minRank = min(minRank, recursiveRank);
        }
        
        return minRank;
    }
    
    private void formGraph(int n, IList<vector<int>> connections) {
        graph = new unordered_map<int, List<int>>();
        rank = new unordered_map<int, int?>();
        connDict = new unordered_map<(int, int), bool>();
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
            rank[i] = null;
        }
        
        foreach (var edge in connections) {
            int u = edge[0], v = edge[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
            connDict[(min(u, v), max(u, v))] = true;
        }
    }
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private HashMap<int, List<int>> graph;
    private HashMap<int, int?> rank;
    private HashMap<(int, int), boolean> connDict;
    
    public List<IList<int>> CriticalConnections(int n, List<IList<int>> connections) {
        formGraph(n, connections);
        dfs(0, 0);
        
        var result = new List<List<int>>();
        foreach (var conn in connDict.Keys) {
            result.add(new List<int> { conn.Item1, conn.Item2 });
        }
        return result;
    }
    
    private int dfs(int node, int discoveryRank) {
        if (rank[node] != null) {
            return rank[node].Value;
        }
        
        rank[node] = discoveryRank;
        int minRank = discoveryRank + 1;
        
        foreach (var neighbor in graph[node]) {
            if (rank[neighbor] != null && rank[neighbor] == discoveryRank - 1) {
                continue;
            }
            
            int recursiveRank = dfs(neighbor, discoveryRank + 1);
            
            if (recursiveRank <= discoveryRank) {
                connDict.Remove((Math.min(node, neighbor), Math.max(node, neighbor)));
            }
            
            minRank = Math.min(minRank, recursiveRank);
        }
        
        return minRank;
    }
    
    private void formGraph(int n, List<IList<int>> connections) {
        graph = new HashMap<int, List<int>>();
        rank = new HashMap<int, int?>();
        connDict = new HashMap<(int, int), boolean>();
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
            rank[i] = null;
        }
        
        foreach (var edge in connections) {
            int u = edge[0], v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
            connDict[(Math.min(u, v), Math.max(u, v))] = true;
        }
    }
}

JavaScript solution

matched/original
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;
        }
    }
}

Python solution

matched/original
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        self.graph = defaultdict(list)
        self.rank = {}
        self.connDict = {}
        
        self.formGraph(n, connections)
        self.dfs(0, 0)
        
        result = []
        for conn in self.connDict:
            result.append(list(conn))
        return result

    def dfs(self, node, discoveryRank):
        if node in self.rank:
            return self.rank[node]
        
        self.rank[node] = discoveryRank
        minRank = discoveryRank + 1
        
        for neighbor in self.graph[node]:
            if neighbor in self.rank and self.rank[neighbor] == discoveryRank - 1:
                continue
            
            recursiveRank = self.dfs(neighbor, discoveryRank + 1)
            
            if recursiveRank <= discoveryRank:
                self.connDict.pop((min(node, neighbor), max(node, neighbor)), None)
            
            minRank = min(minRank, recursiveRank)
        
        return minRank

    def formGraph(self, n, connections):
        for i in range(n):
            self.graph[i]
            self.rank[i] = None
        
        for u, v in connections:
            self.graph[u].append(v)
            self.graph[v].append(u)
            self.connDict[(min(u, v), max(u, v))] = True

Go solution

matched/original
type Solution struct {
    graph    map[int][]int
    rank     map[int]int
    connDict map[[2]int]bool
}

func (s *Solution) CriticalConnections(n int, connections [][]int) [][]int {
    s.formGraph(n, connections)
    s.dfs(0, 0)
    
    var result [][]int
    for conn := range s.connDict {
        result = append(result, []int{conn[0], conn[1]})
    }
    return result
}

func (s *Solution) dfs(node, discoveryRank int) int {
    if r, ok := s.rank[node]; ok {
        return r
    }
    
    s.rank[node] = discoveryRank
    minRank := discoveryRank + 1
    
    for _, neighbor := range s.graph[node] {
        if neighRank, ok := s.rank[neighbor]; ok && neighRank == discoveryRank-1 {
            continue
        }
        
        recursiveRank := s.dfs(neighbor, discoveryRank+1)
        
        if recursiveRank <= discoveryRank {
            delete(s.connDict, [2]int{min(node, neighbor), max(node, neighbor)})
        }
        
        minRank = min(minRank, recursiveRank)
    }
    
    return minRank
}

func (s *Solution) formGraph(n int, connections [][]int) {
    s.graph = make(map[int][]int)
    s.rank = make(map[int]int)
    s.connDict = make(map[[2]int]bool)
    
    for i := 0; i < n; i++ {
        s.graph[i] = []int{}
    }
    
    for _, edge := range connections {
        u, v := edge[0], edge[1]
        s.graph[u] = append(s.graph[u], v)
        s.graph[v] = append(s.graph[v], u)
        s.connDict[[2]int{min(u, v), max(u, v)}] = true
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Построение графа и инициализация:

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

Инициализируйте ранги для узлов.

Поиск в глубину (DFS):

Реализуйте функцию dfs для обхода графа.

Обновите ранги узлов и определите минимальный ранг для текущего узла.

Проверьте, можно ли удалить текущее соединение, и обновите минимальный ранг.

Поиск критических соединений:

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

😎