1085. Minimum Edges to Make Graph Strongly Connected

Given a directed graph with n nodes and edges, return the minimum number of directed edges to add so the whole graph becomes strongly connected. If it is already strongly connected (or has a single node), return 0. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the minimum edges to add.

Examples

Input: {"n":2,"edges":[[0,1]]}
Output: 1
Explanation: Add 1->0 to close the cycle.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: 0
Explanation: Already strongly connected.

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

Constraints

• 1<=n<=10^5
• directed

Asked by