fork download
copy 
  1. use std::io::prelude::*;
  2. use std::cmp;
  3.  
  4. #[macro_use] extern crate scan_fmt;
  5.  
  6. struct UnionFind {
  7.     p: Vec<Option<usize>>,
  8.     s: Vec<usize>,
  9. }
  10. impl UnionFind {
  11.     fn new(size: usize) -> UnionFind {
  12.         UnionFind {
  13.             p: vec![None; size],
  14.             s: vec![1; size],
  15.         }
  16.     }
  17.     fn unite(&mut self, u: usize, v: usize) -> bool {
  18.         let u = self.root(u);
  19.         let v = self.root(v);
  20.         if u == v { return false; }
  21.         if self.s[u] < self.s[v] {
  22.             self.s[u] += self.s[v];
  23.             self.p[v] = Some(u);
  24.         } else {
  25.             self.s[v] += self.s[u];
  26.             self.p[u] = Some(v);
  27.         }
  28.         return true;
  29.     }
  30.  
  31.     fn root(&self, u: usize) -> usize {
  32.         match self.p[u] {
  33.             Some(v) => return self.root(v),
  34.             None    => return u,
  35.         }
  36.     }
  37. }
  38.  
  39. fn main() {
  40.     let mut size = 0usize;
  41.     let mut edges = vec![];
  42.     let stdin = std::io::stdin();
  43.  
  44.     for line in stdin.lock().lines() {
  45.         let (u, v, w) = scan_fmt!(&line.unwrap(), "{} {} {}", usize, usize, i32);
  46.         let u = u.unwrap();
  47.         let v = v.unwrap();
  48.         let w = w.unwrap();
  49.         edges.push((u, v, w));
  50.         size = cmp::max(size, u+1);
  51.         size = cmp::max(size, v+1);
  52.     }
  53.     let size = size;
  54.     edges.sort_by(|e1, e2| e1.2.cmp(&e2.2));
  55.  
  56.     let mut uf = UnionFind::new(size);
  57.     let mut ans = 0;
  58.  
  59.     for e in edges {
  60.         let (i, j, w) = e;
  61.         if uf.unite(i,j) {
  62.             ans += w;
  63.             println!("{} {} {}", i, j, w);
  64.         }
  65.     }
  66.     println!("{}", ans);
  67. }
  68.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
0 1 2
0 2 2
0 3 2
1 2 1
1 3 1
2 3 1
compilation info 
error[E0463]: can't find crate for `scan_fmt`
 --> prog.rs:4:14
  |
4 | #[macro_use] extern crate scan_fmt;
  |              ^^^^^^^^^^^^^^^^^^^^^^ can't find crate

error: aborting due to previous error
stdout
copy 
Standard output is empty
https://ideone.com/btOI2y
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!