Here is the full algorithm:
Create color array of size , all initialized to .
For each node from to : if color[i] == -1, start BFS from .
In BFS: color start node , add to queue.
While queue not empty: pop node, check all neighbors. If neighbor uncolored, give opposite color, add to queue. If neighbor has same color, return false.
If all BFS complete without conflict, return true.
This runs in time and uses space.