q054.rs

use proconio::{fastout, input, marker::Usize1};
use std::collections::VecDeque;
const NIL: i32 = -1;
const AUTHORS: usize = 100000;
const PAPERS: usize = 100000;

#[derive(Debug)]
struct Graph {
    n: usize,
    to: Vec<Vec<usize>>,
    dist: Vec<i32>,
}
impl Graph {
    fn new(n: usize, r: Vec<Vec<usize>>) -> Self {
        let mut to = vec![vec![]; AUTHORS + PAPERS];
        for (paper, rauthors) in r.iter().enumerate() {
            let paper = paper + AUTHORS;
            for &author in rauthors {
                to[author].push(paper);
            }
            to[paper] = (*rauthors).to_owned();
        }
        let dist = vec![NIL; AUTHORS + PAPERS];
        Self { n, to, dist }
    }
    fn bfs(&mut self, n: usize) {
        let mut q = VecDeque::<_>::new();
        q.push_back(n);
        self.dist[n] = 0;
        while let Some(x) = q.pop_front() {
            for &y in &self.to[x] {
                if self.dist[y] != NIL {
                    continue;
                }
                self.dist[y] = self.dist[x] + (y < AUTHORS) as i32;
                q.push_back(y);
            }
        }
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        r: [[Usize1]],
    };
    let mut g = Graph::new(n, r);
    g.bfs(0);
    for i in 0..n {
        println!("{}", g.dist[i]);
    }
}