Editorial for Bipartite Check

Use this editorial only when stuck, and do not 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$ , then run BFS through its component. Whenever we traverse an edge from $u$ to $v$ , vertex $v$ must have the opposite color from $u$ .

If $v$ has not been colored yet, assign that opposite color and continue. If $v$ was already colored the same as $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)$ .

Implementation

Code 1

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()

Comments0

No comments yet

Be the first to comment.

Editorial for Bipartite Check

Approach

Implementation

Comments0

New comment