Parallel Courses

Problem Id: 1136 Difficulty: Medium


Intuition

Solution


class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        # Convert all indexes to be in [0, N-1]
        relations = [(r[0] - 1, r[1] - 1) for r in relations]

        # Build the graph
        graph = DiGraph(N)
        for q, p in relations:
            graph.add_edge(p, q)

        depth = Depth(graph)

        if not all(depth.visited):
            return -1
        return depth.depth()