結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
![]() |
提出日時 | 2024-02-16 18:51:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 1,345 bytes |
コンパイル時間 | 11,990 ms |
コンパイル使用メモリ | 401,964 KB |
実行使用メモリ | 34,196 KB |
最終ジャッジ日時 | 2024-09-28 19:35:26 |
合計ジャッジ時間 | 14,680 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
use std::{collections::{HashMap, HashSet}, io::stdin}; fn main() { let nm = input(); let n = nm[0]; let m = nm[1]; let c = input(); let mut uf = UnionFind::new(n); for _ in 0..m { let uv = input(); let u = uv[0] - 1; let v = uv[1] - 1; if c[u] == c[v] { uf.union(u, v); } } let mut map = HashMap::new(); for i in 0..n { map.entry(c[i]).or_insert_with(|| HashSet::new()).insert(uf.find(i)); } let ret = map.iter().map(|(_k, v)| v.len()-1).sum::<usize>(); println!("{}", ret); } fn input() -> Vec<usize> { let mut buf = String::new(); stdin().read_line(&mut buf).unwrap(); buf.split_whitespace().map(|token| token.parse().unwrap()).collect::<Vec<usize>>() } pub struct UnionFind { parent: Vec<usize> } impl UnionFind { pub fn new(n: usize) -> Self { let parent = (0..n).collect::<Vec<_>>(); UnionFind{ parent} } pub fn find(&mut self, x: usize) -> usize { if self.parent[x] == x { return x; } self.parent[x] = self.find(self.parent[x]); self.parent[x] } pub fn union(&mut self, x: usize, y: usize) { let x = self.find(x); let y = self.find(y); if x != y { self.parent[x] = y; } } }