Course Schedule

warning: unused imports: `Reverse`, `max`, `min`
 --> input/code.rs:1:16
  |
1 | use std::cmp::{max, min, Reverse};
  |                ^^^  ^^^  ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `BinaryHeap`, `HashMap`, `HashSet`
 --> input/code.rs:2:24
  |
2 | use std::collections::{BinaryHeap, HashMap, HashSet};
  |                        ^^^^^^^^^^  ^^^^^^^  ^^^^^^^

warning: 2 warnings emitted

use std::cmp::{max, min, Reverse};
use std::collections::{BinaryHeap, HashMap, HashSet};
use std::io::{self, Read};
use std::process::exit;

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
mod homework;

fn main() {
    // println!("{}", "-".repeat(20));
    // classes::c13::task2();
    homework::hw5::task2();
    // println!("{}", "-".repeat(20));
}
// */

pub fn dfs(u: usize, visited: &mut Vec<usize>, g: &Vec<Vec<usize>>, res: &mut Vec<usize>){
    if visited[u] != 2 {
        if visited[u] == 1 {
            println!("IMPOSSIBLE");
            exit(0);
        }

        visited[u] = 1;

        for v in &g[u] {
            dfs(*v, visited, g, res);
        }

        visited[u] = 2;
        res.push(u);
    }
}


fn main() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let (n, m): (usize, usize) = (input!(it), input!(it));

    let mut in_degree = vec![0_usize; n];
    let mut g: Vec<Vec<usize>> = vec![vec![]; n];

    for _ in 0..m {
        let (u, v): (usize, usize) = (input!(it), input!(it));
        g[u-1].push(v-1);
        in_degree[v-1]+=1;
    }

    let mut res: Vec<usize> = vec![];
    let mut visited: Vec<usize> = vec![0; n];

    // Start DFS from ALL nodes with in-degree 0 (roots)
    for i in 0..n {
        if in_degree[i] == 0 {
            dfs(i, &mut visited, &g, &mut res);
        }
    }

    if res.len() != n {
        println!("IMPOSSIBLE");
    } else {
        res.reverse();  // Reverse to get correct topological order
        for x in res {
            print!("{} ", x + 1);
        }
        println!();
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED