Cod sursa(job #2653305)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 27 septembrie 2020 17:19:03
Problema Sortare topologica Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.41 kb
use std::fs;
use std::fs::File;
use std::io::{BufRead, BufReader, BufWriter, Write, Read};
use std::cmp;
use std::i32::MAX;

const INF:i32 = MAX;

fn dfs(act : &usize, vis : &mut Vec<bool>, stack: &mut Vec<usize>, adj: &Vec<Vec<usize>>){
    vis[*act] = true;

    for i  in adj[*act].iter(){
        if vis[*i] == false{
            dfs(i, vis, stack, adj);
        }
    }

    stack.push(*act);
}

fn main() {
    let mut FIN = BufReader::new(File::open("sortaret.in").unwrap());
    let mut FOUT = BufWriter::new(File::create("sortaret.out").unwrap());

    let mut line = String::new();
    FIN.read_line(&mut line).unwrap();

    let mut data: Vec<i32> = line.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let n : usize = data[0] as usize;
    let m : usize = data[1] as usize;

    let mut adj: Vec<Vec<usize>> = vec![vec![]; n + 1];

    for i in 0..m{
        line.clear();
        FIN.read_line(&mut line).unwrap();
        data = line.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();

        let x = data[0] as usize;
        let y = data[1] as usize;

        adj[x].push(y);
    }

    let mut vis : Vec<bool> = vec![false; n + 1];
    let mut stack : Vec<usize> = vec![];

    for i in 1..(n + 1){
        if vis[i] == false{
            dfs(&i, &mut vis, &mut stack, &adj);
        }
    }

    for i in stack.iter().rev(){
        FOUT.write(format!("{} ", i).as_bytes()).unwrap();
    }
}