AtCoder Beginner Contest 411 F

https://atcoder.jp/contests/abc411/tasks/abc411_f

単にエッジの片方のノードを潰して、もう片方のノードに辺を集約します。そのときに減った辺の数を数えます。集約する方のノードは、UnionFindのrootになる方のノードとします。正確には、両方のノードのrootを潰したり集約したりします。

// Contraction
#![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()
}


//////////////////// UnionFind ////////////////////

use std::cmp::max;

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn is_root(&self, v: Node) -> bool {
        self.parents[v] == v
    }
    
    fn is_connected(&self, u: Node, v: Node) -> bool {
        self.root(u) == self.root(v)
    }
    
    fn connect(&mut self, u: Node, v: Node) {
        let r1 = self.root(u);
        let r2 = self.root(v);
        if r1 == r2 {
            return
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        if self.is_root(v0) {
            v0
        }
        else {
            let p = self.parents[v0];
            self.root(p)
        }
    }
}


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

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

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    (v[0] - 1, v[1] - 1)
}

use std::collections::HashSet;

struct Graph {
    g: Vec<HashSet<Node>>,
    uf: UnionFind
}

impl Graph {
    fn remove_edge(&mut self, edge: Edge) {
        let (u, v) = edge;
        self.g[u].remove(&v);
        self.g[v].remove(&u);
    }
    
    fn add_edge(&mut self, edge: Edge) {
        let (u, v) = edge;
        self.g[u].insert(v);
        self.g[v].insert(u);
    }
    
    // 統合されるNodeと統合するNode
    fn join(&mut self, u: Node, v: Node) -> (Node, Node) {
        let u1 = self.uf.root(u);
        let v1 = self.uf.root(v);
        self.uf.connect(u1, v1);
        if self.uf.root(u1) == u1 {     // u1に統合される
            (u1, v1)
        }
        else {
            (v1, u1)
        }
    }
    
    // エッジを何本減らしたか
    fn degenerate(&mut self, edge: &Edge) -> usize {
        let (u1, v1) = *edge;
        if self.uf.is_connected(u1, v1) {
            return 0
        }
        
        let (u, v) = self.join(u1, v1);
        let mut added_edges: HashSet<Edge> = HashSet::new();
        let mut removed_edges: HashSet<Edge> = HashSet::new();
        for &w in self.g[v].iter() {
            if w != u {
                added_edges.insert((u, w));
            }
            removed_edges.insert((v, w));
        }
        
        let mut counter: usize = removed_edges.len();
        for (_, w) in removed_edges {
            self.remove_edge((v, w))
        }
        for (_, w) in added_edges {
            if !self.g[u].contains(&w) {
                self.add_edge((u, w));
                counter -= 1
            }
        }
        counter
    }
    
    fn create(N: usize, edges: &Vec<Edge>) -> Graph {
        let mut g: Vec<HashSet<Node>> = vec![HashSet::new(); N];
        for &(u, v) in edges.iter() {
            g[u].insert(v);
            g[v].insert(u);
        }
        let uf = UnionFind::new(N);
        Graph { g, uf }
    }
}


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

fn read_input() -> (usize, Vec<Edge>, Vec<usize>) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    let _Q: usize = read();
    let X: Vec<usize> = read_vec::<usize>().into_iter().map(|x| x-1).collect();
    (N, edges, X)
}

fn F(N: usize, edges: Vec<Edge>, X: Vec<usize>) {
    let mut graph = Graph::create(N, &edges);
    let mut num_edges = edges.len();
    for x in X {
        num_edges -= graph.degenerate(&edges[x]);
        println!("{}", num_edges)
    }
}

fn main() {
    let (N, edges, X) = read_input();
    F(N, edges, X)
}