Submission #1160296

---

Source Code Expand

use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;
use std::collections::VecDeque;
fn exec() {
    let mut sc = Scanner::new();
    let (n, m): (usize, usize) = (sc.ne(), sc.ne());
    let mut uf = UnionFind::new(n);
    let mut edge = Vec::new();
    let mut adj = vec![Vec::new(); n];
    for _ in 0..m {
        let u = sc.ne::<usize>() - 1;
        let v = sc.ne::<usize>() - 1;
        edge.push((u, v));
        uf.unite(u, v);
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut cnt = vec![0i32; n];
    for &(u, _) in &edge {
        cnt[uf.root(u)] += 1;
    }
    let (mut ans1, mut ans2, mut ans3) = (0i64, 0i64, 0i64);
    let mut used = vec![vec![false; 2]; n];
    let mut is_oddcycle = |i: usize| -> bool {
        let mut que = VecDeque::new();
        que.push_back((i, 0));
        used[i][0] = true;;
        while let Some(cur) = que.pop_front() {
            for &nxt in &adj[cur.0] {
                if used[nxt][cur.1 ^ 1] {
                    continue;
                }
                used[nxt][cur.1 ^ 1] = true;
                que.push_back((nxt, cur.1 ^ 1));
            }
        }
        used[i][1]
    };
    for i in 0..n {
        if uf.root(i) != i {
            continue;
        }
        if uf.size(i) == 1 {
            ans3 += 1;
            continue;
        }
        if cnt[uf.root(i)] >= uf.size(i) {
            if is_oddcycle(i) {
                ans2 += 1;
            } else {
                ans1 += 1;
            }
        } else {
            ans1 += 1;
        }
    }
    let mut ans = 0i64;
    ans += (n as i64) * ans3 * 2 - ans3 * ans3;
    ans += 2 * ans1 * ans1;
    ans += ans2 * ans2;
    ans += 2 * ans1 * ans2;
    println!("{}", ans);
}

#[allow(dead_code)]
struct UnionFind {
    data: Vec<i32>,
    group: usize,
}
#[allow(dead_code)]
impl UnionFind {
    fn new(n: usize) -> UnionFind {
        UnionFind {
            data: vec![-1i32; n],
            group: n,
        }
    }

    //経路圧縮のみ
    fn unite(&mut self, x: usize, y: usize) -> bool {
        let x = self.root(x);
        let y = self.root(y);
        if x == y {
            return false;
        }
        self.data[x] += self.data[y];
        self.data[y] = x as i32;
        self.group -= 1;
        true
    }

    fn root(&mut self, x: usize) -> usize {
        if self.data[x] < 0 {
            x
        } else {
            let par = self.data[x] as usize;
            let res = self.root(par);
            self.data[x] = res as i32;
            res
        }
    }

    fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    fn size(&mut self, x: usize) -> i32 {
        let par = self.root(x);
        -self.data[par]
    }
}

fn main() {
    const STACK: usize = 16 * 1024 * 1024;
    let _ = std::thread::Builder::new()
        .stack_size(STACK)
        .spawn(|| { exec(); })
        .unwrap()
        .join()
        .unwrap();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!("parse error, {:?}",
                       String::from_utf8(self.buf[l..r].to_owned()))
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Submission Info

Judge Result