AtCoder Beginner Contest 327 D

https://atcoder.jp/contests/abc327/tasks/abc327_d

とをエッジと考えてグラフを作り、0の隣を1として矛盾が無いか調べます。

// Good Tuple Problem
#![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()
}

fn YesNo(b: bool) -> String {
    return (if b { "Yes" } else { "No" }).to_string()
}


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

type Node = usize;
type Graph = Vec<Vec<Node>>;

fn make_graph(N: usize, A: Vec<usize>, B: Vec<usize>) -> Option<Graph> {
    let mut graph: Graph = vec![vec![]; N];
    for (&u, &v) in A.iter().zip(B.iter()) {
        if u == v {
            return None
        }
        graph[u].push(v);
        graph[v].push(u)
    }
    Some(graph)
}


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

fn read_input() -> (usize, Vec<Node>, Vec<Node>) {
    let v = read_vec();
    let N = v[0];
    let A: Vec<Node> = read_vec::<Node>().into_iter().map(|e| e-1).collect();
    let B: Vec<Node> = read_vec::<Node>().into_iter().map(|e| e-1).collect();
    (N, A, B)
}

fn F(N: usize, A: Vec<usize>, B: Vec<usize>) -> bool {
    let op = make_graph(N, A, B);
    if op.is_none() {
        return false
    }
    
    let graph = op.unwrap();
    let mut X: Vec<i32> = vec![-1; N];
    for u in 0..N {
        if X[u] != -1 {
            continue
        }
        
        let mut stack: Vec<Node> = vec![u];
        X[u] = 0;
        while let Some(v) = stack.pop() {
            for &w in graph[v].iter() {
                if X[w] == X[v] {
                    return false
                }
                else if X[w] == -1 {
                    X[w] = 1 - X[v];
                    stack.push(w)
                }
            }
        }
    }
    true
}

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