Course Schedule

#![allow(unused)]

use std::{io, process::exit};

fn take_tuple() -> (usize, usize) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap());
    (it.next().unwrap(), it.next().unwrap())
}

fn dfs(start: &usize, state: &mut Vec<usize>, adj: &Vec<Vec<usize>>, order: &mut Vec<usize>) {
    for &b in adj[*start].iter() {
        if state[b] == 1 {
            println!("IMPOSSIBLE");
            exit(0);
        } else if state[b] == 0 {
            state[b] = 1;
            dfs(&b, state, adj, order);
        }
    }
    order.push(*start);
    state[*start] = 2;
}

fn main() {
    let (n, m): (usize, usize) = take_tuple();
    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];

    for i in 0..m {
        let (a, b) = take_tuple();
        adj[a - 1].push(b - 1);
    }

    let mut state: Vec<usize> = vec![0; n];
    let mut order: Vec<usize> = Vec::with_capacity(n);

    for u in 0..n {
        if state[u] == 0 {
            state[u] = 1; // now being processed
            dfs(&u, &mut state, &adj, &mut order);
        }
    }

    for i in (0..order.len()).rev() {
        print!("{} ", order[i] + 1);
    }
}

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