1192. Critical Connections in a Network

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

A critical connection is a connection that, if removed, will make some server 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.
```

Constraints:

• `1 <= n <= 10^5`
• `n-1 <= connections.length <= 10^5`
• `connections[i][0] != connections[i][1]`
• There are no repeated connections.

1192. Critical Connections in a Network
``````struct Solution;

#[derive(Debug, Eq, PartialEq, Clone)]
struct Node {
id: usize,
discovery: usize,
lowest: usize,
on_stack: bool,
}

impl Node {
fn new(id: usize) -> Node {
let discovery = std::usize::MAX;
let lowest = std::usize::MAX;
let on_stack = false;
Node {
id,
discovery,
lowest,
on_stack,
}
}
}

impl Solution {
fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = n as usize;
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
for connection in connections {
let u = connection[0] as usize;
let v = connection[1] as usize;
graph[u].push(v);
graph[v].push(u);
}
let mut time = 0;
let mut nodes: Vec<Node> = (0..n).map(Node::new).collect();
let mut res = vec![];
Self::dfs(0, 0, &mut time, &mut nodes, &mut res, &graph);
res
}

fn dfs(
u: usize,
parent: usize,
time: &mut usize,
nodes: &mut Vec<Node>,
edges: &mut Vec<Vec<i32>>,
graph: &[Vec<usize>],
) {
nodes[u].discovery = *time;
nodes[u].lowest = *time;
*time += 1;
for &v in &graph[u] {
if v == parent {
continue;
}
if nodes[v].discovery == std::usize::MAX {
Self::dfs(v, u, time, nodes, edges, graph);
nodes[u].lowest = nodes[u].lowest.min(nodes[v].lowest);
if nodes[v].lowest > nodes[u].discovery {
edges.push(vec![u as i32, v as i32]);
}
} else {
nodes[u].lowest = nodes[u].lowest.min(nodes[v].discovery);
}
}
}
}

#[test]
fn test() {
let n = 4;
let connections = vec_vec_i32![[0, 1], [1, 2], [2, 0], [1, 3]];
let res = vec_vec_i32![[1, 3]];
assert_eq!(Solution::critical_connections(n, connections), res);
let n = 5;
let connections = vec_vec_i32![[1, 0], [2, 0], [3, 0], [4, 1], [4, 2], [4, 0]];
let res = vec_vec_i32![[0, 3]];
assert_eq!(Solution::critical_connections(n, connections), res);
}
``````