Cod sursa(job #3313204)

Utilizator game_difficultyCalin Crangus game_difficulty Data 2 octombrie 2025 20:40:23
Problema Sortare topologica Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.45 kb
use std::error::Error;
use std::fs::File;
#[allow(unused_imports)]
use std::io::{BufRead, BufReader, Read, Write};

const FILE: &'static str = "sortaret";

fn main() -> Result<(), Box<dyn Error>> {
    let mut fin = BufReader::new(File::open(format!("{}.in", FILE)).unwrap());
    let mut fout = File::create(format!("{}.out", FILE)).unwrap();

    let mut buf = String::new();

    fin.read_line(&mut buf)?;
    let [n, m] = buf.trim().split_whitespace().map(|x| x.parse::<usize>().unwrap()).collect::<Vec<_>>()[..] else {
        panic!();
    };

    let mut graf_out = vec![vec![]; n + 1];
    let mut graf_in = vec![vec![]; n + 1];

    for _i in 0..m {
        buf.clear();
        fin.read_line(&mut buf)?;
        let [x, y] = buf.trim().split_whitespace().map(|x| x.parse::<usize>().unwrap()).collect::<Vec<_>>()[..] else {
            panic!();
        };

        graf_out[x].push(y);
        graf_in[y].push(x);
    }

    let mut heads = vec![];

    for i in 1..=n {
        println!("{:?}", graf_in[i]);
        if graf_in[i].len() == 0 {
            heads.push(i);
        }
    }

    while !heads.is_empty() {
        let now = heads.pop().unwrap();
        write!(&mut fout, "{} ", now)?;
        for &node in &graf_out[now] {
            let index = graf_in[node].iter().position(|&x| x == now).unwrap();
            graf_in[node].remove(index);
            if graf_in[node].len() == 0 {
                heads.push(node);
            }
        }
    }

    Ok(())
}