Check whether a graph is Bipartite or Not

The problem, simply

You get an undirected graph: V dots joined by two-way lines. Can you paint every dot red or blue so that every line joins a red dot to a blue dot? No line may join two dots of the same color.

Return true if it can be done and false if it cannot.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every possible way to split the dots into two teams. With V dots there are 2^V splits. Write each split as a number whose bits say red (0) or blue (1), and check every line.

1. For mask from 0 to 2^V - 1, dot i is blue if bit i of mask is 1.
2. If every line has ends of different colors, return true.
3. If no split works, return false.

class BipartiteBrute {
    public static boolean isBipartite(int V, int[][] edges) {
        for (int mask = 0; mask < (1 << V); mask++) {     // every way to split
            boolean ok = true;
            for (int[] e : edges) {
                int a = (mask >> e[0]) & 1, b = (mask >> e[1]) & 1;
                if (a == b) { ok = false; break; }          // friends on the same team
            }
            if (ok) return true;
        }
        return false;
    }
}

How long it takes: 2^V splits, each checked against E lines, O(2^V * E). Only usable for about 20 dots. Extra room: O(1).

Way 2: the clever way

Do not guess. Once one dot has a color, the colors of all dots in its piece are forced. Spread the colors with a waiting line, a queue, and watch for a clash.

1. Set every color to "none".
2. For each dot that still has no color, paint it red and put it in the line. This handles graphs in many pieces.
3. Take a dot from the front. For each neighbor: if it has no color, give it the opposite color and add it to the line. If it has the same color as this dot, return false.
4. When every piece is done without a clash, return true.

class BipartiteBfs {
    public static boolean isBipartite(int V, List<List<Integer>> adj) {
        int[] color = new int[V];
        Arrays.fill(color, -1);                     // -1 means no team yet
        for (int start = 0; start < V; start++) {
            if (color[start] != -1) continue;       // already painted by an earlier ripple
            color[start] = 0;
            Queue<Integer> line = new ArrayDeque<>();
            line.add(start);
            while (!line.isEmpty()) {
                int u = line.poll();
                for (int v : adj.get(u)) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];    // the other team
                        line.add(v);
                    } else if (color[v] == color[u]) {
                        return false;               // two friends on one team
                    }
                }
            }
        }
        return true;
    }
}

How long it takes: each dot enters the line once and each line is looked at from both ends, O(V + E). Extra room: the color array and the queue, O(V).

Another way: depth first painting

The same idea works with recursion. Paint a dot, then walk into each unpainted neighbor with the other color. A clash anywhere sends false all the way back up.

class BipartiteDfs {
    public static boolean isBipartite(int V, List<List<Integer>> adj) {
        int[] color = new int[V];
        Arrays.fill(color, -1);
        for (int i = 0; i < V; i++) {
            if (color[i] == -1 && !paint(i, 0, adj, color)) return false;
        }
        return true;
    }

    static boolean paint(int u, int c, List<List<Integer>> adj, int[] color) {
        color[u] = c;
        for (int v : adj.get(u)) {
            if (color[v] == -1) {
                if (!paint(v, 1 - c, adj, color)) return false;
            } else if (color[v] == c) {
                return false;
            }
        }
        return true;
    }
}

Same O(V + E) time. The recursion can go V calls deep, so on a long chain of a million dots the BFS version is safer.

Watch out for

• Using a visited array alone is not enough. You need the color itself to spot a clash.
• A dot with a line to itself (a self-loop) can never be split. The check color[v] == color[u] catches it.
• LeetCode gives graph[i] as the neighbor list of i directly; the code is the same with graph[u] instead of adj.get(u).

What interviewers ask next

• Why does an odd loop make it impossible? Colors must flip at every step, so after an odd number of steps you come back with the wrong color. A graph is two-colorable exactly when it has no odd loop.
• Can you do it with union find? Yes. For each dot, all of its neighbors must be on one team, so union them together. If a dot ends up in the same set as one of its neighbors, return false.
• How do you print the two teams? Collect dots by color at the end.
• "Possible bipartition": people who dislike each other must be in different groups. It is this exact problem on the dislike graph.
• Where is this used? Matching problems: jobs to workers, students to projects. Matching algorithms first need the two sides.

Remember this

Grown-up words: dots are vertices, lines are edges, the two teams are the two parts of a bipartite graph, painting with two colors is 2-coloring, the ripple is breadth first search with a queue, and the pieces are connected components.