Two cabinets

A teaching lab owns two lockable cabinets. Some pairs of reagents react if they share a cabinet, and the technician wants to know whether tonight's delivery can be shelved at all.

The problem

The delivery holds bottles bottles, numbered 0 to bottles - 1, and comes with a list of clashes. Each clash [a, b] means bottles a and b must go in different cabinets. The rule is mutual, a bottle never clashes with itself, and a pair is listed at most once.

Every bottle has to be shelved, and there are only two cabinets. Either cabinet may hold any number of bottles, including none. Return True if some arrangement respects every clash, and False otherwise.

Input. bottles — an integer. clashes — a list of [a, b] pairs.

Output. True or False.

Example.

bottles = 4, clashes = [[0,1], [1,2], [2,3], [3,0]]  ->  True

The clashes form a ring of four. Put 0 and 2 in the left cabinet, 1 and 3 in the right, and no clashing pair shares a cabinet.

Example.

bottles = 3, clashes = [[0,1], [1,2], [2,0]]  ->  False

A ring of three. Put 0 left and 1 right; bottle 2 clashes with both, and there is no third cabinet.

Constraints.

• 1 <= bottles <= 10^5
• 0 <= len(clashes) <= 10^5
• 0 <= a, b < bottles and a != b
• The clashes need not involve every bottle; some have none.

Hints

Approach

Brute force

Try both cabinets for every bottle: 2ⁿ arrangements, each checked in O(E). At 40 bottles that is already 10¹² checks, and the constraints allow 10⁵.

The insight

The first bottle of a connected group can go anywhere; after that every other bottle in the group is forced, so one walk either shelves them all or hits a contradiction.

Shelving a bottle fixes its clashing neighbours in the other cabinet, which fixes theirs back in the first, and so on. Every bottle in a group ends up with a cabinet decided by the parity of its distance from the start. A contradiction appears only when a clash joins two bottles of equal parity — that is, when the clashes contain a ring of odd length. Groups are independent, so start a fresh walk in each, on either cabinet: swapping the two cabinets of a whole group changes nothing else.

Algorithm

1. Build adjacency lists from the clashes.
2. Keep cabinet[b] as 0 for unshelved, 1 and 2 for the two cabinets.
3. For each unshelved bottle, put it in cabinet 1 and start a queue.
4. Pop a bottle, and for each bottle it clashes with: if that one already sits in the same cabinet, return False; if it is unshelved, put it in the other cabinet and queue it.
5. Every group survives — return True.

Complexity

Time O(V + E) — each bottle is queued once, each clash looked at twice. Space O(V + E) for the lists and the queue.

Solution

"""Two cabinets — a breadth-first two-colouring of the incompatibility graph."""

from collections import deque


def solve(bottles, clashes):
    rivals = [[] for _ in range(bottles)]
    for a, b in clashes:
        rivals[a].append(b)
        rivals[b].append(a)

    cabinet = [0] * bottles             # 0 = unshelved, 1 and 2 = the two cabinets
    for start in range(bottles):
        if cabinet[start]:
            continue
        cabinet[start] = 1
        queue = deque([start])
        while queue:
            bottle = queue.popleft()
            other = 3 - cabinet[bottle]  # invariant: a rival always takes the other cabinet
            for rival in rivals[bottle]:
                if cabinet[rival] == cabinet[bottle]:
                    return False
                if not cabinet[rival]:
                    cabinet[rival] = other
                    queue.append(rival)
    return True

TESTS = [
    # A four-bottle ring alternates cleanly between the two cabinets.
    ((4, [[0, 1], [1, 2], [2, 3], [3, 0]]), True),
    # A three-bottle ring cannot: the third clashes wherever it goes.
    ((3, [[0, 1], [1, 2], [2, 0]]), False),
    # Any odd ring fails, however long.
    ((5, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]), False),
    # Two separate groups, each fine on its own.
    ((6, [[0, 1], [2, 3], [4, 5], [1, 2]]), True),
    # No clashes at all: everything goes in one cabinet.
    ((6, []), True),
    # An odd ring hiding in the second group, which a walk from bottle 0 misses.
    ((7, [[0, 1], [2, 3], [3, 4], [4, 2]]), False),
    # A long even chain, deeper than a recursive colouring would survive.
    ((4000, [[i, i + 1] for i in range(3999)]), True),
]

Pitfalls

• Walking from bottle 0 only. A delivery whose clashes split into two groups leaves the second group unshelved, and an impossible second group reports True — the case bottles = 7, clashes = [[0,1], [2,3], [3,4], [4,2]].
• Keeping a separate shelved flag next to the cabinet number. One array with 0 for unshelved is shorter and removes the state where a bottle is marked shelved but never assigned.
• Recursing over a chain of 10⁵ bottles. The interpreter stops near 1,000 frames. Use an explicit queue or stack.

Variants

• The pneumatic post — one walk again, carrying a low-link number up the tree instead of a parity down it.
• Repatching the rig — the same per-component loop, counting the components rather than colouring them.