A farm has fields 0 .. n-1. Some pipes are already laid: existing is a list of pairs (a, b), and water flows both ways through them. The farmer can also lay new pipes from a quote list options of (a, b, cost). Water must be able to reach every field from every other field (through any chain of pipes).
Implement extra_cost(n, existing, options) -> int | None: the minimum total cost of new pipes needed so that all fields are connected, or None if even laying every option isn't enough. Existing pipes are free and can't be removed.
existing = [(0, 1), (2, 3)]
options = [(1, 2, 7), (0, 3, 4), (3, 4, 2), (0, 4, 9), (1, 3, 5)]
extra_cost(5, existing, options) # 6 lay (3, 4) for 2 and (0, 3) for 4
extra_cost(3, [], [(0, 1, 1)]) # None: field 2 can't be reached
extra_cost(2, [(0, 1)], [(0, 1, 3)]) # 0: already connected
Constraints: 1 <= n <= 10^5, up to 10^5 existing pipes, up to 2 * 10^5 options, 1 <= cost <= 10^6. The same pair may appear more than once.
Show hint
Kruskal with union-find: first union every existing pipe (for free), then walk the options in increasing cost and pay for one only when it joins two different groups.