AtCoder Beginner Contest 269 D

https://atcoder.jp/contests/abc269/tasks/abc269_d

グラフを連結成分に分けます。グラフの表現にはHashMapを使います。Vecでも表せるのですが、連結成分に分けるとなると効率が悪くなります。実際には分ける必要は無いのですが、後で使うために分けるコードを書きました。

// Do use hexagon grid
#![allow(non_snake_case)]

use std::ops::Add;
use std::collections::{HashSet, HashMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

#[derive(Clone, Copy)]
#[derive(Debug)]
#[derive(Eq, Hash, PartialEq)]
struct Point {
    x: i32,
    y: i32,
}

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}


//////////////////// Graph ////////////////////

struct Graph {
    g: HashMap<usize, Vec<usize>>
}

impl Graph {
    fn divide_into_connected(&self) -> Vec<Graph> {
        let mut subgraphs = Vec::<Graph>::new();
        let mut unvisited = self.g.keys().map(|v| *v).
                                    collect::<HashSet<usize>>();
        while !unvisited.is_empty() {
            let v0 = unvisited.iter().next().unwrap();
            let mut g = HashMap::<usize, Vec<usize>>::new();
            let mut stack: Vec<usize> = vec![*v0];
            while !stack.is_empty() {
                let v = stack.pop().unwrap();
                let vs = self.g.get(&v).unwrap();
                let vs_copy = vs.iter().map(|v1| *v1).
                                        collect::<Vec<usize>>();
                g.insert(v, vs_copy);
                unvisited.remove(&v);
                for v1 in vs.iter() {
                    if unvisited.contains(v1) {
                        stack.push(*v1);
                        unvisited.remove(v1);
                    }
                }
            }
            subgraphs.push(Graph { g })
        }
        subgraphs
    }
}


//////////////////// process ////////////////////

fn read_input() -> Vec<Point> {
    let N: usize = read();
    (0..N).map(|_| read_vec()).
            map(|v| Point { x: v[0], y: v[1] }).collect()
}

fn create_graph(cells: Vec<Point>) -> Graph {
    let m = cells.iter().zip(0..).map(|(pt, i)| (*pt, i)).
                        collect::<HashMap<Point, usize>>();
    let dirs = vec![(-1, -1), (-1, 0), (0, -1), (0, 1), (1, 0), (1, 1)].
                iter().map(|&(x, y)| Point { x, y }).collect::<Vec<Point>>();
    let neighbors = |&pt| -> Vec<usize> {
        dirs.iter().map(|&dir| pt + dir).filter(|nei| m.contains_key(nei)).
                    map(|nei| *m.get(&nei).unwrap()).collect::<Vec<usize>>()
    };
    let g: HashMap<usize, Vec<usize>> = cells.iter().enumerate().
                            map(|(i, pt)| (i, neighbors(pt))).collect();
    Graph { g }
}

fn f(cells: Vec<Point>) -> usize {
    let graph = create_graph(cells);
    graph.divide_into_connected().len()
}

fn main() {
    let cells = read_input();
    println!("{}", f(cells))
}