LeetCode 886 Possible Bipartition - Algorithm

The algorithm is almost identical to :

$1.$ Build adjacency list from dislikes.

$2.$ Create color array of size $n+1$, all $-1$.

$3.$ For each person $i$ from $1$ to $n$: if color[i] == -1, run BFS from $i$.

$4.$ In BFS: color start as $0$.

For each neighbor: if uncolored, assign opposite color, add to queue. If same color, return false.

$5.$ If all done without conflict, return true.

This runs in $O(V + E)$ time and uses $O(V)$ space.