DAG Longest Path Levels

Problem

Assign each node of a DAG the length of the longest path that ends at it.

Source nodes with no incoming edges get level 0, and every node's level is the maximum over its predecessors of level + 1. Process nodes with Kahn's algorithm so each level is final before it is used. Return the level list, or an empty list when the graph contains a cycle.

Hint

Relax level[v] = max(level[v], level[u] + 1) while peeling indegree-zero nodes.

Test cases

case 1

in: [4,[[0,1],[0,2],[1,3],[2,3]]]

expected: [0,1,1,2]

case 2

in: [3,[[0,1],[1,2]]]

expected: [0,1,2]

case 3

in: [3,[[0,1],[1,2],[2,0]]]

expected: []

case 4

in: [4,[[1,2],[1,3],[0,2]]]

expected: [0,0,1,1]

case 5

in: [1,[]]

expected: [0]

Starter codePython

def dag_longest_levels(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor