1
use std::collections::HashMap;
2

3
const FROM: usize = 0;
4
const TO: usize = 1;
5
const DEFAULT_FACTION: bool = true;
6

7
impl Solution {
8
  /**
9
   * Approach: model the "dislikes" as a graph; it is possible to create a
10
   *           bi-partition iff there is no cycle in the graph.
11
   * Runtime complexity: O(|V|+|E|)
12
   * Space complexity:  O(|V|+|E|)
13
   * N.B.: approach doesn't depend on `n`, but purely on the number of "dislikes".
14
   */
15
  pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
16
    if dislikes.is_empty() {
17
      // If no one dislikes any one, we can create any arbitrary bi-partition.
18
      return true;
19
    }
20
    // Create an undirected graph with all "dislike" relationships (a.k.a. edges).
21
    // The graph may be sparse, so we use an adjacency list:
22
    let mut graph = HashMap::new();
23
    for edge in dislikes.iter() {
24
      graph.entry(edge[FROM]).or_insert(Vec::new()).push(edge[TO]);
25
      graph.entry(edge[TO]).or_insert(Vec::new()).push(edge[FROM]);
26
    }
27
    // For all nodes involved in a "dislike" relationship, heck if there is a cycle in the graph -- a.k.a. conflict among factions:
28
    let mut factions = HashMap::new();
29
    graph.keys().all(|&u| {
30
      if factions.contains_key(&u) {
31
        true
32
      } else {
33
        no_conflict(u, DEFAULT_FACTION, &mut factions, &graph)
34
      }
35
    })
36
  }
37
}
38

39
/**
40
 * Run a depth-first search, recursively, and either:
41
 * - check if there is any conflict with known factions, or
42
 * - set the faction and recurse, flipping the faction at every step along the way.
43
 */
44
fn no_conflict(
45
  u: i32,
46
  faction: bool,
47
  factions: &mut HashMap<i32, bool>,
48
  graph: &HashMap<i32, Vec<i32>>,
49
) -> bool {
50
  if let Some(&actual_faction) = factions.get(&u) {
51
    return actual_faction == faction;
52
  }
53
  factions.insert(u, faction);
54
  graph
55
    .get(&u)
56
    .unwrap()
57
    .iter()
58
    .all(|&v| no_conflict(v, !faction, factions, &graph))
59
}