CodingGyan

Is the Graph Bipartite?

medium Data Structures and Algorithms

Problem

A graph is bipartite if its nodes can be colored with two colors so that every edge joins two different colors. The first line has n and m (nodes 0 to n-1, m undirected edges). The next m lines are the edges. Print true if the graph is bipartite, else false. The graph can have several separate parts. An edge from a node to itself makes it not bipartite.

Constraints

  • 1 <= n <= 10^5
  • 0 <= m <= 2 * 10^5

Examples

Input

4 4
0 1
1 2
2 3
3 0

Output

true

Input

3 3
0 1
1 2
2 0

Output

false

Solutions

Best approachTime O(n + m)Space O(n + m)

A graph is bipartite exactly when it has no cycle of odd length. BFS coloring finds a conflict if one exists. Remember to start from every uncolored node, because one BFS only covers one connected part.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Check bipartite.
 * Input   : n and m, then m edges.
 * Output  : true or false.
 * Approach: BFS coloring.
 * Time    : O(n + m)
 * Space   : O(n + m)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(String[] lines) {
        String[] header = lines[0].split(" ");
        int n = Integer.parseInt(header[0]);

        // Step 1: Build the adjacency lists of the undirected graph.
        java.util.List<java.util.List<Integer>> neighbours = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            neighbours.add(new java.util.ArrayList<>());
        }
        for (int i = 1; i < lines.length; i++) {
            String[] edge = lines[i].split(" ");
            int x = Integer.parseInt(edge[0]);
            int y = Integer.parseInt(edge[1]);
            neighbours.get(x).add(y);
            neighbours.get(y).add(x);
        }

        // Step 2: color[v] is -1 (not colored), 0 or 1. We try to give neighbours different colors.
        int[] color = new int[n];
        java.util.Arrays.fill(color, -1);

        // Step 3: Start a BFS from every node that is not colored yet, because the graph can have several parts.
        for (int start = 0; start < n; start++) {
            if (color[start] != -1) {
                continue;
            }
            color[start] = 0;
            java.util.ArrayDeque<Integer> queue = new java.util.ArrayDeque<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int next : neighbours.get(node)) {
                    if (color[next] == -1) {
                        color[next] = 1 - color[node];
                        queue.add(next);
                    } else if (color[next] == color[node]) {
                        // Step 4: Two neighbours with the same color: the graph is not bipartite.
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. Which cycles make a graph not bipartite?

Try these next