# 2023-02-13：力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号 它们之

2023-02-13：力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号

“关键连接”是在该集群中的重要连接，也就是说，假如我们将它移除

tarjan算法。

``````use std::iter::repeat;
fn main() {
let n = 4;
let connections: Vec<Vec<i32>> = vec![vec![0, 1], vec![1, 2], vec![2, 0], vec![1, 3]];
let ans = unsafe { Solution::critical_connections(n, connections) };
println!("ans = {:?}", ans);
}

static mut DFN: [i32; 100010] = [0; 100010];
static mut LOW: [i32; 100010] = [0; 100010];
static mut DFN_CNT: i32 = 0;
struct Solution {}
impl Solution {
pub unsafe fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut graph: Vec<Vec<i32>> = repeat(vec![]).take(n as usize).collect();
for edge in connections.iter() {
graph[edge[0] as usize].push(edge[1]);
graph[edge[1] as usize].push(edge[0]);
}
for i in 0..n {
DFN[i as usize] = 0;
LOW[i as usize] = 0;
}

DFN_CNT = 0;
let mut ans: Vec<Vec<i32>> = vec![];
Solution::tarjan(0, -1, &mut graph, &mut ans);
return ans;
}

// tarjan  dfs过程
// 点的编号是cur，dfn X low X
unsafe fn tarjan(cur: i32, father: i32, graph: &mut Vec<Vec<i32>>, ans: &mut Vec<Vec<i32>>) {
// 第一次来到cur
// 分配dfn、low序号
DFN_CNT += 1;
LOW[cur as usize] = DFN_CNT;
DFN[cur as usize] = LOW[cur as usize];
let n = graph[cur as usize].len() as i32;
for j in 0..n {
let next = graph[cur as usize][j as usize];
if next != father {
if DFN[next as usize] == 0 {
// 下级的节点没跑过，就去跑
Solution::tarjan(next, cur, graph, ans);
LOW[cur as usize] = get_min(LOW[cur as usize], LOW[next as usize]);
} else {
// 下级的节点跑过了，直接更新low
LOW[cur as usize] = get_min(LOW[cur as usize], DFN[next as usize]);
}
}
}
if LOW[cur as usize] == DFN[cur as usize] && cur != 0 {
ans.push(vec![father, cur]);
}
}
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
``````

(=￣ω￣=)··· 暂无内容！

227

11

20

6