A user's collection is a list of boards, and each board is a list of distinct positive integers: the ids of the pins saved to it. The same pin can be saved to several boards, which is what links boards together.
Two pins are related if you can get from one to the other by hopping between a pin and a board it is on: pin -> board -> another pin on that board -> another board that pin is on -> ... So any two pins on the same board are related, and relation is transitive through shared pins.
Implement:
def related_pins(boards: list[list[int]], queries: list[tuple[int, int]]) -> list[bool]
For each query (p, q) return whether p and q are related, in query order.
Rules:
- A pin that isn't on any board is related to nothing, not even to itself:
(7, 7)isFalseif pin 7 appears nowhere. - A pin that is on at least one board is related to itself:
(p, p)isTrue. - Boards can be empty. Pin ids can be large (up to 10^9).
boards = [[1, 2], [2, 3], [4], [5, 6, 4], []]
related_pins(boards, [(1, 3), (3, 1), (1, 4), (6, 4), (4, 4), (9, 9)])
# [True, True, False, True, True, False]
# 1-2 share board 0, 2-3 share board 1; 4, 5, 6 are linked by board 3
Constraints: up to 100,000 boards with 300,000 pin entries in total, and up to 100,000 queries. Searching the graph from scratch for every query is too slow.
Show hint
Union-find over pin ids (a dict parent map works for sparse ids). For every board, union each pin with the board's first pin. Then a query is two finds. Use path compression (and union by size) so deep chains stay cheap.