AtCoder Beginner Contest 436 E

https://atcoder.jp/contests/abc436/tasks/abc436_e

例えば、3 2 1 4 5という列があったとすると、3と1を入れ替えればいいですよね。位置1にある3は本来の位置3に戻さなければならないです。このように、今ある数とその位置は関係があって、それを結べばグラフになって、さきほどの例は1と3を結ぶループになっています。このグラフは隣のノード数は必ず2になっているので、ループになるか孤立した点になります。連結成分に分解されたループを問題の操作をして本来の位置に戻すにはループ上のノードの数-1であることが分かります。そして、ループ上のどの2点を入れ替えてもループが分裂します。これで本来の位置まで戻す回数は1減っていることが分かります（例えば、6ノードのループが3ノードの2つのループに分裂すれば、5回が2+2=4回に減っている）。すなわち、ループ上のどの2点を入れ替えても最短の操作になります。つまり、連結成分のそれぞれのノード数をとすれば、初期操作の回数は、

となります。

// Minimum Swap
#![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 = usize;
type Edge = (Node, Node);

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

impl Graph {
    fn len(&self) -> usize {
        self.g.len()
    }
    
    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 ////////////////////

fn read_input() -> Vec<usize> {
    let _N: usize = read();
    let P = read_vec::<usize>().into_iter().map(|p| p-1).collect();
    P
}

fn make_edges(P: &Vec<usize>) -> Vec<Edge> {
    let N = P.len();
    let mut edges: HashSet<Edge> = HashSet::new();
    for i in 0..N {
        if P[i] > i {
            edges.insert((i, P[i]));
        }
        else if P[i] < i {
            edges.insert((P[i], i));
        }
    }
    edges.into_iter().collect::<Vec<Edge>>()
}

fn F(P: Vec<usize>) -> usize {
    let edges = make_edges(&P);
    let graph = Graph::create(edges);
    let subgraphs = graph.divide_into_connected();
    subgraphs.into_iter().map(|g| g.len()).
                            map(|n| n*(n-1)/2).sum::<usize>()
}

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