fork download
copy 
  1. #[derive(Default)]
  2.  
  3. struct Graph {
  4.   n: usize,
  5.   m: usize,
  6.   head: Vec<usize>,
  7.   next: Vec<usize>,
  8.   src: Vec<usize>,
  9.   dst: Vec<usize>,
  10.   weight: Vec<isize>,
  11. }
  12.  
  13. impl Graph {
  14.   fn new(n: usize) -> Graph {
  15.     Graph { n: n, m: 0, head: vec![!0; n], .. Default::default() }
  16.   }
  17.   fn add_edge(&mut self, u: usize, v: usize, w: isize) -> usize {
  18.     self.next.push(self.head[u]);
  19.     self.src.push(u);
  20.     self.dst.push(v);
  21.     self.weight.push(w);
  22.     self.head[u] = self.m;
  23.     self.m += 1;
  24.     self.m
  25.   }
  26. }
  27.  
  28. struct UnionFind {
  29.   parent: Vec<usize>,
  30.   size: Vec<usize>,
  31. }
  32. impl UnionFind {
  33.   fn new(n: usize) -> UnionFind {
  34.     UnionFind { parent: vec![!0;n], size: vec![1;n] }
  35.   }
  36.   fn root(&mut self, u: usize) -> usize {
  37.     if self.parent[u] == !0 {
  38.       u
  39.     } else {
  40.       let p = self.parent[u];
  41.       self.parent[u] = self.root(p);
  42.       self.parent[u]
  43.     }
  44.   }
  45.   fn unite(&mut self, u: usize, v: usize) -> bool {
  46.     let mut u = self.root(u);
  47.     let mut v = self.root(v);
  48.     if u == v { 
  49.       return false;
  50.     }
  51.     if self.size[u] > self.size[v] {
  52.       std::mem::swap(&mut u, &mut v);
  53.     }
  54.     self.parent[v] = u;
  55.     self.size[u] += self.size[v];
  56.     true
  57.   }
  58. }
  59.  
  60. fn kruskal(g: Graph) -> Graph {
  61.   let mut es: Vec<usize> = (0..g.m).collect();
  62.   es.sort_by_key(|&i| g.weight[i]);
  63.  
  64.   let mut mst = Graph::new(g.n);
  65.   let mut uf = UnionFind::new(g.n);
  66.   // for e in es { // <- es を消費してしまうので NG (thx: @qnighty)
  67.   for &e in &es {
  68.     if uf.unite(g.src[e], g.dst[e]) {
  69.       mst.add_edge(g.src[e], g.dst[e], g.weight[e]);
  70.     }
  71.   }
  72.   return mst;
  73. }
  74.  
  75. fn main() {
  76.   let mut g = Graph::new(5);
  77.   g.add_edge(0,1,3);
  78.   g.add_edge(1,2,1);
  79.   g.add_edge(2,3,4);
  80.   g.add_edge(3,4,1);
  81.   g.add_edge(4,0,5);
  82.   let mst = kruskal(g);
  83.   for e in 0 .. mst.m {
  84.     println!("({},{},{})", mst.src[e], mst.dst[e], mst.weight[e])
  85.   }
  86. }
  87.  
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(1,2,1)
(3,4,1)
(0,1,3)
(2,3,4)
https://ideone.com/xe523r
language:
Rust (rust 1.56)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!