competitive/graph/
minimum_spanning_tree.rs

1use super::{EdgeListGraph, UnionFind};
2
3impl EdgeListGraph {
4    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
5    where
6        T: Ord,
7    {
8        let mut idx: Vec<_> = (0..self.edges_size()).collect();
9        idx.sort_by_key(weight);
10        let mut uf = UnionFind::new(self.vertices_size());
11        let mut res = vec![false; self.edges_size()];
12        for eid in idx.into_iter() {
13            let (u, v) = self[eid];
14            res[eid] = uf.unite(u, v);
15        }
16        res
17    }
18}