Possible bipartition

/*
 * We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.
 * Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.
 * Example 1:
 * Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
 * Output: true
 * Explanation: The first group has [1,4], and the second group has [2,3].
 * Example 2:
 * Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
 * Output: false
 * Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
 * Constraints:
 * 1 <= n <= 2000
 * 0 <= dislikes.length <= 104
 * dislikes[i].length == 2
 * 1 <= ai < bi <= n
 * All the pairs of dislikes are unique.
 */

use std::collections::VecDeque;

impl Solution {
  pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
    let n = n as usize;
    let mut adj = vec![vec![]; n + 1];
    for d in &dislikes {
      adj[d[0] as usize].push(d[1] as usize);
      adj[d[1] as usize].push(d[0] as usize);
    }
    let mut color = vec![0i32; n + 1];
    for start in 1..=n {
      if color[start] != 0 { continue; }
      color[start] = 1;
      let mut q = VecDeque::new();
      q.push_back(start);
      while let Some(u) = q.pop_front() {
        for &v in &adj[u] {
          if color[v] == 0 {
            color[v] = -color[u];
            q.push_back(v);
          } else if color[v] == color[u] {
            return false;
          }
        }
      }
    }
    true
  }
}