Course Schedule

from collections import deque

def find_course_order(n, m, prerequisites):
    # Create the graph and in-degree array
    graph = [[] for _ in range(n + 1)]
    in_degree = [0] * (n + 1)
    
    # Build the graph and in-degree array
    for a, b in prerequisites:
        graph[a].append(b)
        in_degree[b] += 1
    
    # Initialize the queue with courses that have no prerequisites (in-degree 0)
    queue = deque([i for i in range(1, n + 1) if in_degree[i] == 0])
    
    # Result list to store the topological order
    order = []
    
    # Kahn's algorithm (BFS)
    while queue:
        course = queue.popleft()
        order.append(course)
        
        # For each course dependent on the current course
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            # If the in-degree of a neighbor becomes 0, add it to the queue
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If we were able to process all the courses, return the order
    if len(order) == n:
        return order
    else:
        return "IMPOSSIBLE"

# Input parsing
n, m = map(int, input().split())
prerequisites = [tuple(map(int, input().split())) for _ in range(m)]

# Find and output the course order
result = find_course_order(n, m, prerequisites)

if result == "IMPOSSIBLE":
    print(result)
else:
    print(" ".join(map(str, result)))

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