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
mlines: a rivalryu 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).