Dependency Projectivity Check

Problem

Check whether a dependency tree is projective. arcs is a list of [head, dependent] pairs with positions 0 to n-1; use -1 as head for root nodes.

An arc h to d is projective when every position between h and d is a descendant of h. Build the tree, compute DFS entry and exit times, and test every arc. Return a boolean.

Hint

Crossing arcs are exactly the non-projective configurations in dependency trees.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

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

expected: false

case 4

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

expected: true

case 5

in: [[],1]

expected: true

Starter codePython

def is_projective(arcs, n):
    # Your code here
    pass

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