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

use crate::{
    union_find_low_memory_with_trait::*,
    union_find_traits::*,
};

// TODO: make edge type generic.
/// O(E\log{E})

pub fn mst_kruskcal(
    v_size: usize,
    undirected_edges: Vec<(usize, usize, i64)>,
) -> Vec<usize> {
    let mut uf = UnionFind::new(v_size);

    let mut edges: Vec<(usize, (usize, usize, i64))> =
        undirected_edges.into_iter().enumerate().collect();

    edges.sort_by_key(|&(_, (.., w))| w);

    let mut added = Vec::with_capacity(v_size - 1);

    for (i, (u, v, _)) in edges {
        if uf.same(u, v) {
            continue;
        }

        uf.unite(u, v);

        added.push(i);
    }

    debug_assert!(added.len() == v_size - 1);

    added
}

// TODO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}