Kruskal
(graph/kruskal/src/lib.rs)

• View this file on GitHub
• Last update: 2025-05-28 17:52:35+09:00

Description

Depends on

• Union Find (data-structure/union-find/src/lib.rs)

Verified with

• verification/aizu-online-judge/grl_2_a/src/main.rs

Code

use union_find::UnionFind;

#[derive(Debug, Clone, Copy)]
pub struct Edge {
    from: usize,
    to: usize,
    cost: i64,
}

impl Edge {
    pub fn new(from: usize, to: usize, cost: i64) -> Self {
        Self { from, to, cost }
    }
}

#[derive(Debug, Clone)]
pub struct Kruskal {
    size: usize,
    edge: Vec<Edge>,
}

impl Kruskal {
    pub fn new(size: usize) -> Self {
        Self { size, edge: vec![] }
    }

    pub fn add_edge(&mut self, from: usize, to: usize, cost: i64) {
        self.edge.push(Edge::new(from, to, cost));
    }

    pub fn minimum_spanning_tree(&mut self) -> (i64, Vec<Edge>) {
        self.edge.sort_by(|a, b| a.cost.cmp(&b.cost));
        let mut uf = UnionFind::new(self.size);
        let mut res = 0;
        let mut res_edge = vec![];
        for edge in &self.edge {
            if uf.same(edge.from, edge.to) {
                continue;
            }
            uf.merge(edge.from, edge.to);
            res += edge.cost;
            res_edge.push(edge.clone());
        }
        (res, res_edge)
    }

    pub fn maximum_spanning_tree(&mut self) -> (i64, Vec<Edge>) {
        self.edge.sort_by(|a, b| b.cost.cmp(&a.cost));
        let mut uf = UnionFind::new(self.size);
        let mut res = 0;
        let mut res_edge = vec![];
        for edge in &self.edge {
            if uf.same(edge.from, edge.to) {
                continue;
            }
            uf.merge(edge.from, edge.to);
            res += edge.cost;
            res_edge.push(edge.clone());
        }
        (res, res_edge)
    }
}

pub fn minimum_spanning_tree(size: usize, edge: &mut Vec<(usize, usize, i64)>) -> (i64, Vec<(usize, usize, i64)>) {
    edge.sort_by(|a, b| a.2.cmp(&b.2));
    let mut uf = UnionFind::new(size);
    let mut res = 0;
    let mut res_edge = vec![];
    for &mut (from, to, cost) in edge {
        if uf.same(from, to) {
            continue;
        }
        uf.merge(from, to);
        res += cost;
        res_edge.push((from, to, cost));
    }
    (res, res_edge)
}

pub fn maximum_spanning_tree(size: usize, edge: &mut Vec<(usize, usize, i64)>) -> (i64, Vec<(usize, usize, i64)>) {
    edge.sort_by(|a, b| b.2.cmp(&a.2));
    let mut uf = UnionFind::new(size);
    let mut res = 0;
    let mut res_edge = vec![];
    for &mut (from, to, cost) in edge {
        if uf.same(from, to) {
            continue;
        }
        uf.merge(from, to);
        res += cost;
        res_edge.push((from, to, cost));
    }
    (res, res_edge)
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page