Another classic question, and another from the archives. This one’s nice enough where I took a stab at it in Python for readability.

class Solution(object):
    def isBipartite(self, graph):
        color = {}
        wl = []
        for x, ns in enumerate(graph):
            if x in color: continue
            wl = [x]
            color[x] = 1
            while wl:
                u = wl.pop()
                for w in graph[u]:
                    if w in color and color[w] == color[u]: return False
                    if w not in color:
                        color[w] = 1 - color[u]
                        wl.append(w)
        return True

Thoughts

• The 1 - color[u] trick is handy. It’s a quick way to have 2 options, sort of like not‘ing a boolean variable. Something to teach new people.
• I think there is the possibility that many of the same node is added to wl. I think I need another seen set to make sure we’re not iterating too often. Well, it passed.
• The outermost loop is always a bit annoying: it’d be nice to promise that the graph is always connected. It’s good to know how to handle that situation, so I suppose that’s OK.
• The term color here is because a bipartite graph is the same as a 2-colorable graph. Graph-coloring is a core combinatoric question. This solution overall follows from the observation that “if U is on the left, then all neighbors of U must be on the right, and vice-versa”. Instead of left/right, we use 2 colors (which in this case are… integers).
• This is basically an extension of DFS. There is probably an opportunity for more cleverness.

Finally, a graph algorithm! More to come, I imagine. They’re all collected here.