結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
![]() |
提出日時 | 2024-02-16 18:20:06 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,695 bytes |
コンパイル時間 | 13,934 ms |
コンパイル使用メモリ | 406,624 KB |
実行使用メモリ | 27,924 KB |
最終ジャッジ日時 | 2024-09-28 19:33:47 |
合計ジャッジ時間 | 22,395 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 TLE * 1 -- * 11 |
ソースコード
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 g = vec![vec![]; n]; for _ in 0..m { let uv = input(); let u = uv[0] - 1; let v = uv[1] - 1; g[u].push(v); g[v].push(u); } let mut map = HashMap::new(); for i in 0..n { map.entry(c[i]).or_insert_with(|| vec![]).push(i); } let mut ret = 0; for (_color, curs) in map { let mut uf = UnionFind::new(n); for &cur in &curs { for &nxt in &g[cur] { if c[cur] == c[nxt] { uf.union(cur, nxt) } } } let mut groups = HashSet::new(); for &cur in &curs { groups.insert(uf.find(cur)); } ret += groups.len()-1; } 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 { parents: Vec<usize> } impl UnionFind { pub fn new(size: usize) -> Self { let parents = (0..size).collect::<Vec<_>>(); UnionFind{ parents } } pub fn find(&mut self, x: usize) -> usize { if self.parents[x] == x { return x; } self.parents[x] = self.find(self.parents[x]); self.parents[x] } pub fn union(&mut self, x: usize, y: usize) { let x = self.find(x); let y = self.find(y); if x != y { self.parents[x] = self.parents[y] } } }