HardNLPnlp-117

Projective Order Check

Problem

Return True when every dependency arc is projective: for an arc from h to d, every token strictly between h and d must have h among its ancestors.

heads[i] is the parent of token i, with -1 marking a root. An empty head list is projective.

Hint

A crossing arc leaves a token between its endpoints that is not dominated by the head.

case 1

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

expected: false

case 2

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

expected: true

case 3

in: [[-1,0,0,0]]

expected: true

case 4

in: [[]]

expected: true

Starter codePython

def projective_order_check(heads):
    # Your code here
    pass

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