結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
![]() |
提出日時 | 2024-02-16 18:42:28 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 1,489 bytes |
コンパイル時間 | 27,728 ms |
コンパイル使用メモリ | 398,612 KB |
実行使用メモリ | 36,424 KB |
最終ジャッジ日時 | 2024-09-28 19:35:05 |
合計ジャッジ時間 | 15,953 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
warning: fields `parent` and `size` are never read --> src/main.rs:63:5 | 62 | pub struct UnionFind { | --------- fields in this struct 63 | parent: Vec<usize>, | ^^^^^^ 64 | size: Vec<usize>, | ^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
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 parent = (0..n).collect::<Vec<usize>>(); let mut visited = vec![false; n]; for start in 0..n { if visited[start] { continue } let mut stack = vec![start]; while !stack.is_empty() { let cur = stack.pop().unwrap(); visited[cur] = true; parent[cur] = start; for &nxt in &g[cur] { if c[cur]==c[nxt] && !visited[nxt] { stack.push(nxt); } } } } 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 groups = HashSet::new(); for &cur in &curs { groups.insert(parent[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 { parent: Vec<usize>, size: Vec<usize>, }