Bipartite Check

The Idea

Colour the start node, colour every neighbour the opposite, and keep going. If you ever reach a neighbour that already carries your own colour, the split is impossible — an odd cycle is hiding in there. It is ordinary BFS with one extra field per node, so the cost stays O(V + E).

Real-World Example

Seating rivals at a wedding. Nobody may sit at a table with someone they feud with, and there are two tables. Assign the first guest, push every rival to the other table, and repeat. A three-way feud collapses the plan immediately.

The Code

from collections import deque
g = {"ann": ["bob", "cy"], "bob": ["ann", "dee"],
     "cy": ["ann", "dee"], "dee": ["bob", "cy"]}

colour = {"ann": 0}
q = deque(["ann"])
ok = True
while q:
    n = q.popleft()
    for m in g[n]:
        if m not in colour:
            colour[m] = 1 - colour[n]    # opposite side of the split
            q.append(m)
        elif colour[m] == colour[n]:     # neighbours share a side
            ok = False

print(ok, colour)
# True {'ann': 0, 'bob': 1, 'cy': 1, 'dee': 0}

from collections import deque
g = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
colour, q, ok = {1: 0}, deque([1]), True
while q:
  n = q.popleft()
  for m in g[n]:
      if m not in colour:
          colour[m] = 1 - colour[n]
          q.append(m)
      elif colour[m] == colour[n]:
          ok = False
print(ok)