1114. Minimum Equivalent Graph via Transitive Reduction

Given a directed acyclic graph with n nodes and edges, return the number of edges in its transitive reduction — the minimum equivalent graph that preserves exactly the same reachability between all pairs of nodes. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the number of edges in the transitive reduction.

Examples

Input: {"n":3,"edges":[[0,1],[1,2],[0,2]]}
Output: 2
Explanation: The 0->2 edge is implied by 0->1->2.

Input: {"n":3,"edges":[[0,1],[0,2]]}
Output: 2
Explanation: Both edges are needed.

Input: {"n":1,"edges":[]}
Output: 0
Explanation: No edges.

Constraints

• 1<=n<=1000
• directed acyclic

Asked by