1040. Minimum Spanning Tree — Number of Edges

Given an undirected weighted graph with n nodes and edges [u, v, w] (possibly disconnected), return the number of edges in its minimum spanning forest — that is, the number of edges Kruskal's algorithm adds, which equals n minus the number of connected components. The input is JSON {n, edges}.

Input: JSON {n, edges} with edges [u, v, w].

Output: Integer — the number of spanning-forest edges.

Examples

Input: {"n":5,"edges":[[0,1,1],[2,3,1]]}
Output: 2
Explanation: Two edges connect two pairs; node 4 is isolated.

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

Input: {"n":3,"edges":[[0,1,2],[1,2,3]]}
Output: 2
Explanation: A connected triple uses n-1=2 edges.

Constraints

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

Asked by