Submission #37814034

---

Source Code Expand

use proconio::input;
use proconio::marker::Usize1;
use rustc_hash::FxHashSet;

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

    let mut ans = 0;
    let mut g = vec![vec![]; n];
    for (a, b) in edges {
        g[a].push(b);
        g[b].push(a);
    }

    let mut path = FxHashSet::default();
    dfs(0, &g, &mut path, &mut ans);

    println!("{}", 1_000_000.min(ans));
}

fn dfs(v:usize, g:&Vec<Vec<usize>>, path:&mut FxHashSet<usize>, ans:&mut usize) {
    *ans += 1;
    path.insert(v);
    if *ans >= 1_000_000 { return; }

    for &u in g[v].iter() {
        if path.contains(&u) { continue }
        dfs(u, g, path, ans);
    }

    path.remove(&v);
}

Submission Info

Judge Result