1
use std::collections::{HashMap, VecDeque};
2
impl Solution {
3
  pub fn sort_items(n: i32, m: i32, group: Vec<i32>, before_items: Vec<Vec<i32>>) -> Vec<i32> {
4
    let mut outer_graph: HashMap<i32, Vec<i32>> = HashMap::new();
5
    let mut inner_graph: HashMap<i32, HashMap<i32, Vec<i32>>> = HashMap::new();
6
    for i in 0..n as usize {
7
      if group[i] == -1 && before_items[i].is_empty() {
8
        outer_graph.entry(i as i32).or_default();
9
      } else if group[i] == -1 {
10
        outer_graph.entry(i as i32).or_default();
11
        for b in &before_items[i] {
12
          let gp = group[*b as usize];
13
          if gp == -1 {
14
            outer_graph.entry(*b).or_default().push(i as i32);
15
          } else {
16
            outer_graph.entry(gp + 40000).or_default().push(i as i32);
17
          }
18
        }
19
      } else {
20
        outer_graph.entry(group[i] + 40000).or_default();
21
        inner_graph
22
          .entry(group[i])
23
          .or_default()
24
          .entry(i as i32)
25
          .or_default();
26
        for b in &before_items[i] {
27
          let gp = group[*b as usize];
28
          if gp == -1 {
29
            outer_graph.entry(*b).or_default().push(group[i] + 40000);
30
          } else if group[i] == gp {
31
            inner_graph
32
              .entry(gp)
33
              .or_default()
34
              .entry(*b)
35
              .or_default()
36
              .push(i as i32);
37
          } else {
38
            outer_graph
39
              .entry(gp + 40000)
40
              .or_default()
41
              .push(group[i] + 40000);
42
          }
43
        }
44
      }
45
    }
46
    if let Some(res) = Self::topo_sort(&outer_graph, &inner_graph) {
47
      if res.len() != n as usize {
48
        return vec![];
49
      }
50
      return res;
51
    } else {
52
      return vec![];
53
    }
54
  }
55

56
  fn topo_sort(
57
    graph: &HashMap<i32, Vec<i32>>,
58
    inner_graph: &HashMap<i32, HashMap<i32, Vec<i32>>>,
59
  ) -> Option<Vec<i32>> {
60
    let mut res: Vec<i32> = vec![];
61
    let mut in_degree: HashMap<i32, i32> = HashMap::new();
62
    let mut queue: VecDeque<i32> = VecDeque::new();
63
    for (k, v) in graph {
64
      in_degree.entry(*k).or_default();
65
      for n in v {
66
        *in_degree.entry(*n).or_default() += 1;
67
      }
68
    }
69
    for (k, v) in &in_degree {
70
      if *v == 0 {
71
        queue.push_back(*k);
72
      }
73
    }
74
    while !queue.is_empty() {
75
      let n = queue.pop_front().unwrap();
76
      if n < 40000 {
77
        res.push(n)
78
      } else {
79
        if let Some(mut s) = Self::topo_sort(&inner_graph[&(n - 40000)], inner_graph) {
80
          if s.len() != inner_graph[&(n - 40000)].len() {
81
            return None;
82
          }
83
          res.append(&mut s);
84
        } else {
85
          return None;
86
        }
87
      }
88
      for v in &graph[&n] {
89
        *in_degree.entry(*v).or_default() -= 1;
90
        if in_degree[v] == 0 {
91
          queue.push_back(*v);
92
        }
93
      }
94
    }
95
    return Some(res);
96
  }
97
}