LeetCode 1192 LintCode 1271 Critical Connections in a Network

Table of contents

Description

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

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

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

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]


Constraints:

2 <= n <= 10^5
n - 1 <= connections.length <= 10^5, e
0 <= a_i, b_i <= n - 1
a_i != b_i

There are no repeated connections.

Solution

Idea

We can use Tarjan’s algorithm to traverse the graph and try to find the topological order. If we encounter a cycle, the edges in the cycle are not critical. We set the rank for the vertexes in the cycle to the minimum rank.

Let’s use example 1 above and go through the iterations of the dfs.

Complexity: Time O(n+e), Space O(n+e).

C++

class Solution {
    vector<int> ranks;
    vector<vector<int>> res;
    vector<vector<int>> adj;
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>> &connections) {
        adj.resize(n);
        ranks.resize(n);
        for (auto &e: connections)
            adj[e[0]].emplace_back(e[1]), adj[e[1]].emplace_back(e[0]);
        for (int v = 0; v < n; v++) dfs(0, v, 1);
        return res;
    }

    void dfs(int p, int v, int rank) {
        if (ranks[v] != 0) return;
        ranks[v] = rank;
        for (int w: adj[v]) {
            if (w == p) continue;
            dfs(v, w, rank + 1);
            ranks[v] = min(ranks[v], ranks[w]);
            if (rank < ranks[w]) res.emplace_back(initializer_list<int>{v, w});
        }
    }
};

Java

class CriticalConnection {
    List<List<Integer>> res;
    List<List<Integer>> adj;
    int[] ranks;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        adj = new ArrayList<>();
        res = new ArrayList<>();
        ranks = new int[n];
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (List<Integer> e : connections) {
            adj.get(e.get(0)).add(e.get(1));
            adj.get(e.get(1)).add(e.get(0));
        }
        dfs(0, 0, 1);
        return res;
    }

    void dfs(int v, int parent, int rank) {
        if (ranks[v] != 0) return;
        ranks[v] = rank;
        for (int w : adj.get(v)) {
            if (w == parent) continue;
            dfs(w, v, rank + 1);
            ranks[v] = Math.min(ranks[v], ranks[w]);
            if (rank < ranks[w]) res.add(Arrays.asList(v, w));
        }
    }
}

Python

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        res = []
        adj, ranks = [[] for _ in range(n)], [0] * n
        for e in connections:
            adj[e[0]].append(e[1])
            adj[e[1]].append(e[0])

        def dfs(v: int, parent: int, rank: int) -> None:
            if ranks[v] != 0: return
            ranks[v] = rank
            for w in adj[v]:
                if w == parent: continue
                dfs(w, v, rank + 1)
                ranks[v] = min(ranks[v], ranks[w])
                if rank < ranks[w]: res.append([v, w])

        dfs(0, 0, 1)
        return res

Rust

impl Solution {
    pub fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut adj = vec![vec![]; n];
        for e in &connections {
            adj[e[0] as usize].push(e[1] as usize);
            adj[e[1] as usize].push(e[0] as usize);
        }
        let mut ranks = vec![0i32; n];
        let mut res = vec![];
        Self::dfs(&adj, &mut ranks, &mut res, 0, 0, 1);
        res
    }

    fn dfs(adj: &[Vec<usize>], ranks: &mut [i32], res: &mut Vec<Vec<i32>>,
           parent: usize, v: usize, rank: i32) {
        if ranks[v] != 0 { return; }
        ranks[v] = rank;
        for &w in &adj[v] {
            if w == parent { continue; }
            Self::dfs(adj, ranks, res, v, w, rank + 1);
            ranks[v] = ranks[v].min(ranks[w]);
            if rank < ranks[w] { res.push(vec![v as i32, w as i32]); }
        }
    }
}