1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
pub fn count_toposort(adj_bits: &[usize]) -> usize {
let g = adj_bits;
let n = g.len();
let mut dp = vec![0; 1 << n];
dp[0] = 1;
for s in 0..1 << n {
for i in 0..n {
if s >> i & 1 == 0 && g[i] & s == 0 {
dp[s | 1 << i] += dp[s];
}
}
}
*dp.last().unwrap()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let cases = vec![
(vec![vec![], vec![0, 2], vec![]], 2),
(vec![vec![1, 3], vec![2], vec![4], vec![4], vec![]], 3),
(
vec![
vec![1],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
vec![],
],
10461394944000usize,
),
];
for (g, ans) in cases {
let n = g.len();
let mut gb = vec![0; n];
for u in 0..n {
for &v in g[u].iter() {
gb[u] |= 1 << v;
}
}
assert_eq!(count_toposort(&gb), ans);
}
}
}