dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

use crate::{
    bit_length_with_count_leading_zeros_usize::bit_length,
    functional_graph_doubling_table::doubling_table,
    tree_bfs_parent_depth::bfs,
};

pub struct LCA {
    pub(crate) depth: Vec<usize>,
    ancestor: Vec<Vec<usize>>,
}

impl LCA {
    pub fn new(
        g: &[Vec<usize>],
        root: usize,
    ) -> Self {
        let (parent, depth) = bfs(g, root);

        let k = bit_length(*depth.iter().max().unwrap());

        let ancestor = doubling_table(&parent, k.max(1));

        Self { ancestor, depth }
    }

    pub fn get(
        &self,
        mut u: usize,
        mut v: usize,
    ) -> usize {
        if self.depth[u] > self.depth[v] {
            std::mem::swap(&mut u, &mut v);
        }

        let dv = self.depth[v] - self.depth[u];

        for (i, a) in self.ancestor.iter().enumerate() {
            if dv >> i & 1 == 1 {
                v = a[v];
            }
        }

        debug_assert_eq!(self.depth[u], self.depth[v]);

        if u == v {
            return u;
        }

        for a in self.ancestor.iter().rev() {
            let (nu, nv) = (a[u], a[v]);

            if nu != nv {
                u = nu;

                v = nv;
            }
        }

        self.ancestor[0][u]
    }
}

#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}