Spare Roads for Two Travellers
Problem
A region has n towns numbered 1 to n and a list of roads [kind, u, v]. A road of kind 1 may be used only by the cyclist, kind 2 only by the driver, and kind 3 by both. The council wants to close as many roads as possible while each traveller can still get from every town to every other town using the roads open to them. Return the largest number of roads that can be closed, or -1 if even the full network fails one of the travellers.
Examples
Input: n = 4, roads = [[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]]
Output: 2
Why: [1, 1, 2] and [1, 1, 3] duplicate links the shared roads already give the cyclistInput: n = 4, roads = [[3, 1, 2], [3, 2, 3], [1, 1, 4], [2, 1, 4]]
Output: 0
Why: every road is needed by at least one travellerInput: n = 4, roads = [[3, 2, 3], [1, 1, 2], [2, 3, 4]]
Output: -1
Why: edge case, the cyclist can never reach town 4 and the driver never town 1Hints
0 / 3
Each traveller needs a spanning tree of the roads open to them, and a spanning tree over n towns has exactly n minus 1 roads. Closing the most roads means keeping the fewest.
A shared road can count towards both trees at once, so it is worth more than a private one. Try to use shared roads before any private road.
Keep two disjoint-set structures, one per traveller. Offer every shared road to both first and keep it if it joins two groups in either structure. Then offer each private road to its own traveller's structure. Keep a road only when it joins two groups, check that both structures end with a single group, and return the number of roads never kept.
Solution
Each traveller needs their open roads to form one connected group, and any road that closes a cycle in a traveller's view is redundant for that traveller. A shared road that joins two groups does the work of two private roads at the cost of one, and any forest of shared roads can later be completed with private ones, so taking every useful shared road before any private road is never worse. Because both travellers see the same shared roads, a shared road joins two groups for one traveller exactly when it does for the other at that stage. Private roads come next, each offered only to its own traveller's structure. If either structure still has more than one group at the end, the task is impossible; otherwise every road that was never kept can be closed. Time is O(m times the inverse Ackermann function) for m roads and space is O(n).
def spare_roads(n, roads):
def dsu():
parent = list(range(n + 1))
def join(a, b): # True if a and b were apart
while parent[a] != a: parent[a] = a = parent[parent[a]]
while parent[b] != b: parent[b] = b = parent[parent[b]]
parent[a] = b
return a != b
return join
cyclist, driver = dsu(), dsu()
kept = joins_c = joins_d = 0
for kind in (3, 1, 2): # shared roads first
for t, u, v in roads:
if t != kind: continue
c = t != 2 and cyclist(u, v)
d = t != 1 and driver(u, v)
joins_c += c; joins_d += d; kept += c or d
if joins_c != n - 1 or joins_d != n - 1:
return -1 # someone is left stranded
return len(roads) - kept
print(spare_roads(4, [[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]])) # -> 2
print(spare_roads(4, [[3, 1, 2], [3, 2, 3], [1, 1, 4], [2, 1, 4]])) # -> 0
print(spare_roads(4, [[3, 2, 3], [1, 1, 2], [2, 3, 4]])) # -> -1Stuck on the idea rather than the code? Components & Cycles covers it.