結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-08-12 13:48:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 7,624 bytes |
コンパイル時間 | 13,192 ms |
コンパイル使用メモリ | 391,336 KB |
実行使用メモリ | 17,396 KB |
最終ジャッジ日時 | 2024-11-14 12:21:56 |
合計ジャッジ時間 | 14,121 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
//https://github.com/rust-lang-ja/ac-library-rspub mod dsu {//! A Disjoint set union (DSU) with union by size and path compression./// A Disjoint set union (DSU) with union by size and path compression.////// See: [Zvi Galil and Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems](https://core.ac.uk/download/pdf/161439519.pdf)////// In the following documentation, let $n$ be the size of the DSU.////// # Example////// ```/// use ac_library::Dsu;/// use proconio::{input, source::once::OnceSource};////// input! {/// from OnceSource::from(/// "5\n\/// 3\n\/// 0 1\n\/// 2 3\n\/// 3 4\n",/// ),/// n: usize,/// abs: [(usize, usize)],/// }////// let mut dsu = Dsu::new(n);/// for (a, b) in abs {/// dsu.merge(a, b);/// }////// assert!(dsu.same(0, 1));/// assert!(!dsu.same(1, 2));/// assert!(dsu.same(2, 4));////// assert_eq!(/// dsu.groups()/// .into_iter()/// .map(|mut group| {/// group.sort_unstable();/// group/// })/// .collect::<Vec<_>>(),/// [&[0, 1][..], &[2, 3, 4][..]],/// );/// ```pub struct Dsu {n: usize,// root node: -1 * component size// otherwise: parentparent_or_size: Vec<i32>,}impl Dsu {/// Creates a new `Dsu`.////// # Constraints////// - $0 \leq n \leq 10^8$////// # Complexity////// - $O(n)$pub fn new(size: usize) -> Self {Self {n: size,parent_or_size: vec![-1; size],}}// `\textsc` does not work in KaTeX/// Performs the Uɴɪᴏɴ operation.////// # Constraints////// - $0 \leq a < n$/// - $0 \leq b < n$////// # Panics////// Panics if the above constraints are not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn merge(&mut self, a: usize, b: usize) -> usize {assert!(a < self.n);assert!(b < self.n);let (mut x, mut y) = (self.leader(a), self.leader(b));if x == y {return x;}if -self.parent_or_size[x] < -self.parent_or_size[y] {std::mem::swap(&mut x, &mut y);}self.parent_or_size[x] += self.parent_or_size[y];self.parent_or_size[y] = x as i32;x}/// Returns whether the vertices $a$ and $b$ are in the same connected component.////// # Constraints////// - $0 \leq a < n$/// - $0 \leq b < n$////// # Panics////// Panics if the above constraint is not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn same(&mut self, a: usize, b: usize) -> bool {assert!(a < self.n);assert!(b < self.n);self.leader(a) == self.leader(b)}/// Performs the Fɪɴᴅ operation.////// # Constraints////// - $0 \leq a < n$////// # Panics////// Panics if the above constraint is not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn leader(&mut self, a: usize) -> usize {assert!(a < self.n);if self.parent_or_size[a] < 0 {return a;}self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;self.parent_or_size[a] as usize}/// Returns the size of the connected component that contains the vertex $a$.////// # Constraints////// - $0 \leq a < n$////// # Panics////// Panics if the above constraint is not satisfied.////// # Complexity////// - $O(\alpha(n))$ amortizedpub fn size(&mut self, a: usize) -> usize {assert!(a < self.n);let x = self.leader(a);-self.parent_or_size[x] as usize}/// Divides the graph into connected components.////// The result may not be ordered.////// # Complexity////// - $O(n)$pub fn groups(&mut self) -> Vec<Vec<usize>> {let mut leader_buf = vec![0; self.n];let mut group_size = vec![0; self.n];for i in 0..self.n {leader_buf[i] = self.leader(i);group_size[leader_buf[i]] += 1;}let mut result = vec![Vec::new(); self.n];for i in 0..self.n {result[i].reserve(group_size[i]);}for i in 0..self.n {result[leader_buf[i]].push(i);}result.into_iter().filter(|x| !x.is_empty()).collect::<Vec<Vec<usize>>>()}}#[cfg(test)]mod tests {use super::*;#[test]fn dsu_works() {let mut d = Dsu::new(4);d.merge(0, 1);assert!(d.same(0, 1));d.merge(1, 2);assert!(d.same(0, 2));assert_eq!(d.size(0), 3);assert!(!d.same(0, 3));assert_eq!(d.groups(), vec![vec![0, 1, 2], vec![3]]);}}}use dsu::*;pub mod scanner {pub struct Scanner {buf: Vec<String>,}impl Scanner {pub fn new() -> Self {Self { buf: vec![] }}pub fn new_from(source: &str) -> Self {let source = String::from(source);let buf = Self::split(source);Self { buf }}pub fn next<T: std::str::FromStr>(&mut self) -> T {loop {if let Some(x) = self.buf.pop() {return x.parse().ok().expect("");}let mut source = String::new();std::io::stdin().read_line(&mut source).expect("");self.buf = Self::split(source);}}fn split(source: String) -> Vec<String> {source.split_whitespace().rev().map(String::from).collect::<Vec<_>>()}}}use crate::scanner::Scanner;use crate::Dsu;use std::io::Write;fn main() {let mut scanner = Scanner::new();let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());let t: usize = 1;for _ in 0..t {solve(&mut scanner, &mut out);}}fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {let n: usize = scanner.next();let m: usize = scanner.next();let mut dsu = Dsu::new(n * 2);for _ in 0..m {let a: usize = scanner.next();let b: usize = scanner.next();dsu.merge(a - 1, b - 1);}let mut ans = 0usize;for g in dsu.groups().iter() {if g.len() % 2 == 1 {ans += 1;}}ans /= 2;writeln!(out, "{}", ans).unwrap();}