CT38820

The Link Budget Beneath Marigold Row

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the saffron fields of Marigold Row with crates of ledgers, and Lakshya the accountant must account for every last one. Task: n isolated nodes are joined by m edges (some may be redundant). Print the minimum number of additional edges needed to make the graph connected. Input format: First line: n and m. Next m lines: u v. Output format: Print the number of extra edges needed. Constraints: 1 <= n <= 4000; 0 <= m <= 4000.

Example 1:

Input: 10 36 1 5 4 8 2 6 5 8 5 7 3 9 3 4 7 8 3 10 4 5 3 5 1 8 8 9 4 10 5 9 6 7 8 10 6 10 4 7 2 10 2 7 1 10 3 7 1 6 4 6 1 2 6 8 4 9 6 9 5 10 2 5 1 7 1 3 2 4 7 9 9 10
Output: 0

Example 2:

Input: 10 23 2 9 3 9 3 10 2 5 4 9 3 7 4 5 5 8 2 6 1 10 1 4 3 6 2 4 3 4 1 7 8 9 2 3 7 9 5 9 7 8 4 6 8 10 1 9
Output: 0

Example 3:

Input: 10 32 4 8 4 9 2 4 2 9 6 8 5 9 2 10 6 9 7 10 1 8 1 6 2 5 1 4 5 7 2 7 1 2 4 7 4 6 1 3 8 10 9 10 3 4 4 10 3 9 5 8 7 9 2 8 3 6 1 10 3 8 6 7 5 10
Output: 0

Constraints:

1 <= n <= 4000; 0 <= m <= 4000.

Loading...
Test Cases:No test cases
No test cases available.
The Link Budget Beneath Marigold Row - MEDIUM Coding Problem | CodeTikki