Loading...
Loading...
Loading...
A college offers n elective courses, numbered 1 to n. Some courses have prerequisites: a pair a b means course a must be finished before course b starts. A student takes one course at a time.
Print an order to take all n courses so that every prerequisite comes first. When more than one course can be taken next, always take the one with the smallest number. This makes the answer unique.
If the prerequisites go round in a loop, so that no order works, print IMPOSSIBLE.
IMPOSSIBLE.Example 1
Input
4 3 1 2 1 3 3 2
Output
1 3 2 4
At the start, courses 1 and 4 are free, so 1 goes first. Then 3 and 4 are free, so 3 goes next. Then 2 and 4 are free, so 2, and 4 last.
Example 2
Input
3 3 1 2 2 3 3 1
Output
IMPOSSIBLE
Each course waits for another one in a loop, so no course can start.
Try the problem first. Open one hint at a time.
A course can be taken once all its prerequisites are done. Count, for every course, how many prerequisites it is still waiting for.
Courses waiting for 0 prerequisites are free. Taking a course lowers the count of every course that needs it.
To always take the smallest free course, keep the free courses in a PriorityQueue instead of a plain queue.
If fewer than n courses were taken when no course is free, some courses are stuck in a loop.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor