Cod sursa(job #3364842)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 12 septembrie 2026 11:56:05
Problema Sortare topologica Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.97 kb
use std::fs::File;
use std::io::{Read, Write, BufWriter};

fn main() {

    let mut input_bytes = Vec::new();
    File::open("sortaret.in")
        .unwrap()
        .read_to_end(&mut input_bytes)
        .unwrap();

    let mut cursor = 0;

    let mut next_num = || -> usize {

        while cursor < input_bytes.len() && input_bytes[cursor] <= b' ' {
            cursor += 1;
        }
        if cursor == input_bytes.len() {
            return 0;
        }
        let mut res = 0;

        while cursor < input_bytes.len() && input_bytes[cursor] > b' ' {
            res = res * 10 + (input_bytes[cursor] - b'0') as usize;
            cursor += 1;
        }
        res
    };

    let n = next_num();
    if n == 0 { return; }
    let m = next_num();

    let mut g = vec![Vec::new(); n + 1];
    let mut in_degree = vec![0; n + 1];

    for _ in 0..m {
        let (x, y) = (next_num(), next_num());
        g[x].push(y);
        in_degree[y] += 1;
    }

    let mut stack = Vec::new();
    for i in 1..=n {
        if in_degree[i] == 0 {
            stack.push(i);
        }
    }

    let mut ans = Vec::with_capacity(n);

    while let Some(node) = stack.pop() {
        ans.push(node);
        for &son in &g[node] {
            in_degree[son] -= 1;
            if in_degree[son] == 0 {
                stack.push(son);
            }
        }
    }

    let mut output_bytes = Vec::with_capacity(n * 8);
    for &node in &ans {
        let mut temp = node;
        let mut digits = [0u8; 10];
        let mut len = 0;

        // Extract digits backwards
        while temp > 0 {
            digits[len] = b'0' + (temp % 10) as u8;
            temp /= 10;
            len += 1;
        }

        while len > 0 {
            len -= 1;
            output_bytes.push(digits[len]);
        }
        output_bytes.push(b' ');
    }

    // Write all bytes at once
    let file = File::create("sortaret.out").unwrap();
    let mut writer = BufWriter::new(file);
    writer.write_all(&output_bytes).unwrap();
}