1045. Sequence Reconstruction Using Topo Sort

Given a permutation 'nums' of 1..n and a list of subsequences 'sequences', determine whether nums is the unique shortest sequence consistent with all the subsequences (i.e. the only valid topological order). Return true or false. The input is JSON {nums, sequences}.

Input: JSON {nums, sequences}.

Output: Boolean — true or false.

Examples

Input: {"nums":[1,2,3],"sequences":[[1,2],[1,3],[2,3]]}
Output: true
Explanation: Order uniquely forced.

Input: {"nums":[1,2,3],"sequences":[[1,2],[1,3]]}
Output: false
Explanation: 2 and 3 order not fixed.

Input: {"nums":[1],"sequences":[[1]]}
Output: true
Explanation: Single element.

Constraints

• 1<=n<=10^4
• nums is a permutation of 1..n

Asked by