結果
問題 | No.1390 Get together |
ユーザー |
![]() |
提出日時 | 2021-03-14 15:03:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 2,072 bytes |
コンパイル時間 | 13,480 ms |
コンパイル使用メモリ | 405,844 KB |
実行使用メモリ | 17,248 KB |
最終ジャッジ日時 | 2024-11-06 05:00:48 |
合計ジャッジ時間 | 17,368 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#[allow(dead_code)]#[allow(unused_imports)]fn read<T: std::str::FromStr>() -> T {use std::io::*;let stdin = stdin();let stdin = stdin.lock();let token: String = stdin.bytes().map(|c| c.expect("failed to read char") as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect();token.parse().ok().expect("failed to parse token")}use std::mem::*;struct UnionFind {par: Vec<i64>,}#[allow(dead_code)]impl UnionFind {pub fn new(n: usize) -> Self {let par = (0..n).map(|_| -1).collect();Self{par}}pub fn root(&mut self, x: usize) -> i64 {if self.par[x] < 0{x as i64}else{self.par[x] = self.root(self.par[x] as usize);self.par[x]}}pub fn same(&mut self, x: usize, y: usize) -> bool {self.root(x) == self.root(y)}pub fn merge(&mut self, x: usize, y: usize) -> bool {let mut _x: i64 = self.root(x);let mut _y: i64 = self.root(y);if _x == _y {return false;}if self.par[_x as usize] > self.par[_y as usize] {swap(&mut _x, &mut _y);}self.par[_x as usize] += self.par[_y as usize];self.par[_y as usize] = _x as i64;return true;}pub fn size(&mut self, x: usize) -> i64 {(self.par[x]) as i64 * -1}}fn main(){let n:usize = read();let m:usize = read();let bc:Vec<(usize,usize)> = (0..n).map(|_| (read(),read())).collect();let mut rec = vec![Vec::new();n];let mut uf = UnionFind::new(m);for i in 0..n {rec[bc[i].1 - 1].push(bc[i].0 - 1);}let mut ans = 0;for i in 0..n {if rec[i].len() == 0 {continue;}let key = rec[i][0];for j in 0..rec[i].len() {if !uf.same(key,rec[i][j]) {ans += 1;uf.merge(key,rec[i][j]);}}}println!("{}",ans);}