add abc399c.rs

rchaser53 · rchaser53 · commit 4711bccc492b · 2025-04-02T18:42:11.000+09:00
diff --git a/src/abc/abc399c.rs b/src/abc/abc399c.rs
@@ -0,0 +1,86 @@
+/** THIS IS AN OUTPUT FILE. NOT EDIT THIS FILE DIRECTLY. **/
+use proconio::input;
+use proconio::marker::*;
+use std::marker::PhantomData;
+use std::cmp::*;
+use std::collections::*;
+
+struct UnionFind {
+  parents: Vec<usize>,
+  sizes: Vec<usize>,
+  ranks: Vec<usize>
+}
+
+impl UnionFind {
+  fn new(n:usize) -> UnionFind {
+    let mut uf = UnionFind { parents: vec![0;n], sizes:vec![1;n], ranks:vec![0;n] };
+    for i in 0..n {
+      uf.parents[i] = i;
+    }
+    uf
+  }
+
+  fn root(&mut self, x:usize) -> usize {
+    let ti = self.parents[x];
+    if ti == x {
+      x
+    } else {
+      self.parents[x] = self.root(ti);
+      self.parents[x]
+    }
+  }
+
+  fn is_same(&mut self, x:usize, y:usize) -> bool {
+    self.root(x) == self.root(y)
+  }
+
+  fn unite(&mut self, x:usize, y:usize) -> bool {
+    let rx = self.root(x);
+    let ry = self.root(y);
+    if rx == ry { return false }
+    let (rx, ry) = if self.ranks[rx] < self.ranks[ry] {
+      (ry, rx)
+    } else {
+      (rx, ry)
+    };
+    self.parents[ry] = rx;
+    if self.ranks[rx] == self.ranks[ry] {
+      self.ranks[rx] += 1;
+    }
+
+    self.sizes[rx] += self.sizes[ry];
+    true
+  }
+
+  fn group_size(&mut self, x:usize) -> usize {
+    let i = self.root(x);
+    self.sizes[i]
+  }
+}
+
+fn main() {
+  input! {
+    n:usize,
+    m:usize,
+    edges: [(Usize1, Usize1);m]
+  }
+
+  let mut ut = UnionFind::new(n);
+
+  for &(a, b) in &edges {
+    ut.unite(a, b);
+  }
+
+  let mut map = HashMap::new();
+  for &(a, _) in &edges {
+    let pi = ut.root(a);
+    *map.entry(pi).or_insert(0) += 1;
+  }
+
+  let mut result = 0;
+  for (i, num) in map {
+    result += num - (ut.group_size(i) - 1);
+  }
+  
+  println!("{}", result);
+}
