AtCoder ABC327 D問題をRustで実装してみた

はじめに

最近、就活関係でアルゴリズムについて聞かれることが多くなり、勉強しようとAtCoderを久しぶりやったら全然解けませんでした。研究ではPythonを多用していますが、競プロにおいてはRustを使いたいと思っているため勉強中です。

今回対象にするのはこの問題です。DFSを使った基礎的な二部グラフ判定の問題です。

• AtCoder ABC327 D問題
• AtCoder ABC327 D問題 公式解説

D問題の公式解説はC++でDFSを使って解いている

詳細な解説は、前述のリンクから読んでください。

Rustで書き換えます。再帰で借用は書いたことなかったため、試行錯誤しながら書きました。色々通って結局これに落ち着きました。

借用とかたいそうな名前がついていますがただのポインタとして扱えば何も問題ないなと一人で勝手に腑に落ちてました。

good_tuple_problem.rs

use proconio::input;
use std::collections::HashSet;

fn dfs(graph: &Vec::<HashSet::<usize>>, x:&mut Vec::<isize>, node:usize, value: usize) -> bool{
    x[node] = value as isize;
    for i in &graph[node] {
        if x[node] == x[*i] || (x[*i] == -1 && !dfs(graph, x, *i, 1 - value)){
            return false;
        }
    }
    return true;
}

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [usize; m],
        b: [usize; m],
    }

    let mut x = vec![-1_isize; n];
    let mut graph = vec![HashSet::<usize>::new(); n];
    for i in 0..m {
        graph[a[i]-1].insert(b[i]-1);
        graph[b[i]-1].insert(a[i]-1);
    }
    let graph = graph;

    for i in 0..n {
        if x[i] == -1 && !dfs(&graph, &mut x, i, 0){
            println!("No");
            std::process::exit(0);
        }
    }
    println!("Yes");
}