Seat guests at two tables with no feud at either

Colour the graph with two colours using BFS: give a starting guest table 0, their rivals table 1, and so on. If a feud ever links two guests with the same table, it is impossible. Repeat from every guest not yet seated, since the graph may have several parts. O(V + E) time and space.

A graph splits this way exactly when it has no cycle of odd length.

Union-find works too: union each guest's rivals together and check no guest shares a set with a rival.

Isolated guests can sit anywhere.

from collections import deque


def two_tables(n: int, feuds: list[list[int]]) -> bool:
    rivals: list[list[int]] = [[] for _ in range(n)]
    # a feud goes both ways
    for u, v in feuds:
        rivals[u].append(v)
        rivals[v].append(u)
    table = [-1] * n
    for first in range(n):
        if table[first] >= 0:
            continue
        table[first] = 0
        queue = deque([first])
        while queue:
            g = queue.popleft()
            for r in rivals[g]:
                if table[r] < 0:
                    table[r] = 1 - table[g]
                    queue.append(r)
                elif table[r] == table[g]:
                    return False
    return True

Common mistakes

• Only starting from guest 0 and missing other parts of the graph.
• Treating feuds as one-way.

Mention the odd-cycle fact; it shows you understand why the BFS check works.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you return the two tables?

   Show hint

   Return the colour list from the BFS.

2. What about three tables?

   Show hint

   Three-colouring is NP-complete in general; small cases need backtracking.