Skills101
← All coding problems

Is the Graph Bipartite?

easyGraphs II+10 XPTime limit 2s

A coach wants to split n players into two teams so that every pair of players who have a rivalry ends up in different teams. Given the rivalries, is it possible? (In graph terms: is the graph bipartite?) A team may be empty.

Input:

  • line 1: n m
  • next m lines: a rivalry u v

Output: true or false.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, u ≠ v, no repeated pairs. The graph may be disconnected.

Think about it: 2-colour the graph with BFS: give the start node colour 0, its neighbours colour 1, their neighbours colour 0, and so on. If an edge ever joins two nodes of the same colour, it is impossible — that happens exactly when the graph has an odd cycle. Start a new BFS from every uncoloured node.

Sample input 1

4 4
1 2
2 3
3 4
4 1

Sample output 1

true

Sample input 2

3 3
1 2
2 3
3 1

Sample output 2

false

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.