BFSをrustで実装

タイトルの通り。
勉強がてら実装してみたという話
参考：https://qiita.com/drken/items/996d80bcae64649a6580#1-2-bfs-%E3%81%AE%E5%AE%9F%E8%A3%85

2次元ベクターの行数は確保したいが列の中身は無い状態にしたいという書き方が
vec![vec![0;0]; n];
で書けるのが発見でした。

22/10/19 : キューがベクタで実装されているのに1年たってから気づいた。修正。たまに時間がかかるときがあると思ったら・・・

main.rs

use proconio::input;

fn main() {
input!{
n:usize,
m:usize,
t:[[usize; 2]; m],
}
let mut gra = vec![vec![0;0]; n];
let mut dist = vec![-1;n];
let mut queue =VecDeque::new();
dist[0]=0;
queue.push_back(0);

for i in &t{
    gra[i[0]].push(i[1]);
    gra[i[1]].push(i[0]);
}


while !queue.is_empty(){
    let v = queue.pop_front().unwrap();

    for nv in &gra[v]{

        if dist[*nv] != -1{continue}

        dist[*nv] = dist[v] + 1;
        queue.push_back(*nv);

    }


}

println!("{:?}",dist)


}

追記
distの保存をするところを連想配列にした。大きさが大きすぎるときはこちらを使う必要がある

fn main() {
  input!{
    m:usize,
    mut t:[[usize; 2]; m],
    }
    
    let mut map = HashMap::new();
    //let mut dist = vec![-1;n];
    let mut queue =VecDeque::new();
    let mut max = 1;
    let mut map2 = HashMap::new();
    queue.push_back(1);
    
    for i in &t{
      map.entry(i[0]).or_insert(vec![i[1]]).push(i[1]);
      map.entry(i[1]).or_insert(vec![i[0]]).push(i[0]) ;

      }
    
    while !queue.is_empty(){
        let v = queue.pop_front().unwrap();
        if map.get(&v) == None{
          continue
        }
        for nv in map.get(&v).unwrap(){
    
            if map2.get(nv) != None{
              continue
            }
            map2.entry(*nv).or_insert(1);
            max = max.max(*nv);
            queue.push_back(*nv);
    
        }
    
    
    }

    println!("{}",max)
  }