SAC '22 Code Challenge 5 Junior P4 - Course Requirements

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Java 1.5s
Memory limit: 256M

Problem type

Since Max is heading off to university, he needs to create a course schedule for N courses.

However, each course has C_i prerequisites, and Max cannot schedule properly.

Can you tell Max the order to take his courses to satisfy the prerequisites?


1 \le N \le 2 \times 10^5

0 \le C_i < N

\sum_{i=1}^N C_i \le \min(\frac{N(N-1)}{2}, 2 \times 10^5)

It is always possible to generate a course schedule that does not conflict (i.e., it is possible to take every course without missing a prerequisite).

Subtask 1 [40%]

1 \le N \le 10

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line will contain an integer, N, the number of courses in the schedule.

The next N lines will contain an integer, C_i, and C_i integers, representing the number of prerequisites for the i^\text{th} course and its prerequisites.

Output Specification

Output any valid permutation of the N courses, where each course is not missing a prerequisite when it is taken.

Sample Input

3 1 2 5
3 1 2 3
1 2

Sample Output

1 2 5 3 4


There are no comments at the moment.