BOJ. Bipartite Graph (1707)

Color the vertices of each test graph with two colors. A graph is bipartite exactly when every edge joins vertices of different colors. The graph may be disconnected, so start a breadth-first search at every vertex that has not been colored yet. During the search, assign each newly discovered neighbor the opposite color. If an edge joins vertices that already have the same color, the graph is not bipartite; this also detects a self-loop.

The invariant is that every processed edge connects opposite colors. BFS extends this valid two-way partition through each component; finding a same-color edge proves no such partition can satisfy all edges. Each vertex and edge is processed only a constant number of times, so the time complexity is O(V + E). The color and queue arrays use O(V) auxiliary space; the adjacency list uses O(V + E) space.

Problem link

Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int testCases = input.nextInt();
        StringBuilder output = new StringBuilder();

        for (int test = 0; test < testCases; test++) {
            int vertexCount = input.nextInt();
            int edgeCount = input.nextInt();
            int[] head = new int[vertexCount];
            java.util.Arrays.fill(head, -1);
            int[] to = new int[2 * edgeCount];
            int[] next = new int[2 * edgeCount];

            for (int edge = 0; edge < edgeCount; edge++) {
                int a = input.nextInt() - 1;
                int b = input.nextInt() - 1;
                to[2 * edge] = b;
                next[2 * edge] = head[a];
                head[a] = 2 * edge;
                to[2 * edge + 1] = a;
                next[2 * edge + 1] = head[b];
                head[b] = 2 * edge + 1;
            }

            int[] color = new int[vertexCount];
            int[] queue = new int[vertexCount];
            boolean bipartite = true;

            for (int start = 0; start < vertexCount && bipartite; start++) {
                if (color[start] != 0) {
                    continue;
                }

                int front = 0;
                int back = 0;
                color[start] = 1;
                queue[back++] = start;
                while (front < back && bipartite) {
                    int vertex = queue[front++];
                    for (int edge = head[vertex]; edge != -1; edge = next[edge]) {
                        int neighbor = to[edge];
                        if (color[neighbor] == 0) {
                            color[neighbor] = 3 - color[vertex];
                            queue[back++] = neighbor;
                        } else if (color[neighbor] == color[vertex]) {
                            bipartite = false;
                            break;
                        }
                    }
                }
            }
            output.append(bipartite ? "YES\n" : "NO\n");
        }
        System.out.print(output);
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }
    }
}