Editorial for Bipartite Check

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Process each connected component independently. Start an unvisited vertex with color $0$ ~0~, then run BFS through its component. Whenever we traverse an edge from $u$ ~u~ to $v$ ~v~, vertex $v$ ~v~ must have the opposite color from $u$ ~u~.

If $v$ ~v~ has not been colored yet, assign that opposite color and continue. If $v$ ~v~ was already colored the same as $u$ ~u~, then this edge cannot join two different colors, so the graph is not bipartite.

Disconnected graphs are handled by starting a new BFS from every vertex that has not already been colored.

The time complexity is $O(n + m)$ ~O(n + m)~.

Implementation

from collections import deque
import sys


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    graph = [[] for _ in range(n)]
    idx = 2
    for _ in range(m):
        a = data[idx] - 1
        b = data[idx + 1] - 1
        idx += 2
        graph[a].append(b)
        graph[b].append(a)

    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue

        color[start] = 0
        q = deque([start])
        while q:
            node = q.popleft()
            next_color = color[node] ^ 1
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = next_color
                    q.append(neighbor)
                elif color[neighbor] == color[node]:
                    print("NO")
                    return

    print("YES")


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.