AtCoder Beginner Contest 412 D

https://atcoder.jp/contests/abc412/tasks/abc412_d

グラフがループのみで構成されるグラフを全て考えればよいです。ループはノード数が3以上でNが8以下なので、ループは2つ以下なのでちょっと楽です。そのグラフのエッジと与えられたエッジの交差を調べれば何回の操作でそのグラフになるを簡単に数えられます。

// Make 2-Regular Graph
#![allow(non_snake_case)]

use std::collections::HashSet;


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

fn permutations<T: Clone>(a: Vec<T>) -> Vec<Vec<T>> {
    let N = a.len();
    if N == 1 {
        vec![a.to_vec()]
    }
    else {
        let mut bs: Vec<Vec<T>> = vec![];
        for i in 0..N {
            let v: Vec<T> = (0..N).filter(|&j| j != i).
                                    map(|j| a[j].clone()).collect();
            let bs_sub = permutations(v);
            for mut b in bs_sub.into_iter() {
                b.insert(0, a[i].clone());
                bs.push(b)
            }
        }
        bs
    }
}

fn combinations<T: Clone>(a: Vec<T>, n: usize) -> Vec<(Vec<T>, Vec<T>)> {
    let N = a.len();
    if n == 0 {
        return vec![(vec![], a)]
    }
    else if n == N {
        return vec![(a, vec![])]
    }
    
    let mut v: Vec<(Vec<T>, Vec<T>)> = vec![];
    for i in 0..N+1-n {
        let b: Vec<T> = (0..N).filter(|&j| j != i).
                                map(|j| a[j].clone()).collect();
        let w = combinations(b, n-1);
        for (w1, w2) in w {
            let mut w3 = w1.to_vec();
            w3.insert(0, a[i].clone());
            v.push((w3, w2))
        }
    }
    v
}


//////////////////// Edge ////////////////////

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

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


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

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

fn perms<T: Clone>(v: Vec<T>) -> Vec<Vec<T>> {
    let N = v.len();
    let v1: Vec<T> = (1..N).map(|i| v[i].clone()).collect();
    let mut w: Vec<Vec<T>> = vec![];
    for v2 in permutations(v1) {
        let mut v3 = v2.to_vec();
        v3.insert(0, v[0].clone());
        w.push(v3)
    }
    w
}

fn divide<T: Clone>(a: Vec<T>) -> Vec<Vec<Vec<T>>> {
    let mut v: Vec<Vec<Vec<T>>> = vec![];
    let N = a.len();
    for perm in perms(a.to_vec()) {
        v.push(vec![perm])
    }
    
    for n1 in 3..N/2+1 {
        let pairs = combinations(a.to_vec(), n1);
        for (b1, b2) in pairs {
            let c1 = perms(b1);
            let c2 = perms(b2);
            for d1 in c1 {
                for d2 in c2.iter() {
                    v.push(vec![d1.to_vec(), d2.to_vec()])
                }
            }
        }
    }
    v
}

fn normalize_edge(edge: Edge) -> Edge {
    let (u, v) = edge;
    if u < v { (u, v) } else { (v, u) }
}

fn divide_loops_into_edges(div: &Vec<Vec<Node>>) -> HashSet<Edge> {
    let mut edges: HashSet<Edge> = HashSet::new();
    for loop_graph in div.iter() {
        let N = loop_graph.len();
        for i in 0..N {
            edges.insert(normalize_edge((loop_graph[i], loop_graph[(i+1)%N])));
        }
    }
    edges
}

use std::cmp::min;

fn F(N: usize, edges: Vec<Edge>) -> usize {
    let set_edges: HashSet<Edge> = edges.iter().
                                    map(|&edge| normalize_edge(edge)).collect();
    let mut min_edges: usize = edges.len() + N;
    let divs = divide((0..N).collect::<Vec<_>>());
    for div in divs {
        let new_edges = divide_loops_into_edges(&div);
        let num = new_edges.intersection(&set_edges).count();
        let num_edges = (N - num) + (edges.len() - num);
        min_edges = min(min_edges, num_edges)
    }
    min_edges
}

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