tipstar0125
commented
1 year ago #[derive(Debug, Clone)]
struct LowLink<'a> {
size: usize,
edge: &'a Vec<Vec<usize>>,
visited: Vec<bool>,
order: Vec<usize>,
low: Vec<usize>,
aps: Vec<usize>,
bridge: Vec<(usize, usize)>,
}
impl<'a> LowLink<'a> {
fn new(edge: &'a Vec<Vec<usize>>) -> Self {
let size = edge.len();
let visited = vec![false; size];
let order = vec![0; size];
let low = vec![0; size];
let aps = vec![];
let bridge = vec![];
LowLink {
size,
edge,
visited,
order,
low,
aps,
bridge,
}
}
fn build(&mut self) {
let mut cnt = 0;
for i in 0..self.size {
if !self.visited[i] {
self.dfs(i, -1, &mut cnt);
}
}
self.aps.sort();
self.bridge.sort();
}
fn dfs(&mut self, pos: usize, parent: isize, cnt: &mut usize) {
self.visited[pos] = true;
self.order[pos] = *cnt;
self.low[pos] = self.order[pos];
*cnt += 1;
let mut is_aps = false;
let mut children_cnt = 0_usize;
for &next in &self.edge[pos] {
if !self.visited[next] {
children_cnt += 1;
self.dfs(next, pos as isize, cnt);
self.low[pos] = self.low[pos].min(self.low[next]);
if parent != -1 && self.order[pos] <= self.low[next] {
is_aps = true;
}
if self.order[pos] < self.low[next] {
self.bridge.push((pos.min(next), pos.max(next)));
}
} else if next as isize != parent {
self.low[pos] = self.low[pos].min(self.order[next]);
}
}
if parent == -1 && children_cnt >= 2 {
is_aps = true;
}
if is_aps {
self.aps.push(pos);
}
}
}
コード参考：https://sen-comp.hatenablog.com/entry/2022/11/17/233858 図解がわかりやすい解説：https://kntychance.hatenablog.jp/entry/2022/09/16/161858 AOJジャッジ：https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3
その他： Rust解説：https://ngtkana.hatenablog.com/entry/2021/10/17/170030 2D Gridのlowlink(Rust)：https://atcoder.jp/contests/toyota2023summer-final/submissions/44994401