AtCoder Beginner Contest 434 E

https://atcoder.jp/contests/abc434/tasks/abc434_e

異なるウサギが同じ位置に行けると問題が生じるので、グラフにすればいいとわかります。入力例1なら、ウサギはそれぞれ3と5、-1と5、-1と9なので、3 - 5 - -1 - 9というグラフになります。そして、エッジがウサギで、エッジごとにどちらかのノードを取って取れる最大のノード数は、入力例1のように木なら順番にたどればいいので、ノード数-1となります。ループがあるなら、これも順番にたどればノード数になります。ループからひげが出ていても同じです。なので、グラフを連結成分に分割して、それぞれのグラフが木かどうかを調べればよいです。

// Distribute Bunnies
#![allow(non_snake_case)]


//////////////////// 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()
}


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

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

type Node = i32;
type Edge = (Node, Node);

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

impl Graph {
    fn len(&self) -> usize {
        self.g.len()
    }
    
    fn is_tree(&self) -> bool {
        let mut visited: HashSet<Node> = HashSet::new();
        let v0 = self.g.keys().next().unwrap();
        let mut stack: Vec<(Node, Node)> = vec![(-1, *v0)];     // (prev, cur)
        while let Some((v1, v2)) = stack.pop() {
            if let Some(vs) = self.g.get(&v2) {
                for &v3 in vs {
                    if v3 == v1 {
                        continue
                    }
                    else if visited.contains(&v3) {
                        return false
                    }
                    else {
                        visited.insert(v3);
                        stack.push((v2, v3))
                    }
                }
            }
        }
        true
    }
    
    fn divide_into_connected(&self) -> Vec<Graph> {
        let mut subgraphs: Vec<Graph> = vec![];
        let mut unvisited: HashSet<Node> = self.g.keys().cloned().collect();
        while let Some(&v0) = unvisited.iter().next() {
            let mut subvs: Vec<Node> = vec![];
            let mut stack: Vec<Node> = vec![v0];
            unvisited.remove(&v0);
            subvs.push(v0);
            while let Some(v) = stack.pop() {
                if let Some(vs) = self.g.get(&v) {
                    for &v1 in vs.iter() {
                        if unvisited.contains(&v1) {
                            unvisited.remove(&v1);
                            stack.push(v1);
                            subvs.push(v1);
                        }
                    }
                }
            }
            
            let mut g: HashMap<Node, Vec<Node>> = HashMap::new();
            for v in subvs {
                if let Some(vs) = self.g.get(&v) {
                    g.insert(v, vs.to_vec());
                }
            }
            subgraphs.push(Graph { g })
        }
        subgraphs
    }
    
    fn create(edges: Vec<Edge>) -> Graph {
        let mut g: HashMap<Node, Vec<Node>> = HashMap::new();
        for (u, v) in edges {
            let e1 = g.entry(u).or_insert(vec![]);
            (*e1).push(v);
            let e2 = g.entry(v).or_insert(vec![]);
            (*e2).push(u)
        }
        Graph { g }
    }
}


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

type Rabbit = (i32, i32);

fn read_rabbit() -> Rabbit {
    let v: Vec<i32> = read_vec();
    (v[0], v[1])
}

fn read_input() -> Vec<Rabbit> {
    let N: usize = read();
    let rabbits: Vec<Rabbit> = (0..N).map(|_| read_rabbit()).collect();
    rabbits
}

fn F(rabbits: Vec<Rabbit>) -> usize {
    let edges: Vec<Edge> = rabbits.into_iter().
                                map(|(X, R)| (X-R, X+R)).collect();
    let graph = Graph::create(edges);
    let subgraphs = graph.divide_into_connected();
    let mut counter: usize = 0;
    for subg in subgraphs {
        counter += subg.len() - (if subg.is_tree() { 1 } else { 0 })
    }
    counter
}

fn main() {
    let rabbits = read_input();
    println!("{}", F(rabbits))
}