haar_lib/tree/
rooted_isomorphism.rs

1//! 根付き木の(根付き)部分木を同型性によって分類する。
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/rooted_tree_isomorphism_classification>
5use crate::tree::*;
6use std::collections::{hash_map::DefaultHasher, HashMap};
7use std::hash::{Hash, Hasher};
8
9/// 根付き木の(根付き)部分木を同型性によって分類する。
10///
11/// # Returns
12/// - `(k, a)` : `k`は部分木の種類数、`a`は頂点`i`と頂点`j`を根とする部分木が同型のときに限り`a[i] = a[j]`を満たす。
13pub fn rooted_isomorphism<E: TreeEdgeTrait>(tree: &Tree<E>, root: usize) -> (usize, Vec<usize>) {
14    let n = tree.len();
15    let mut ret = vec![0; n];
16    let mut map = HashMap::new();
17    let mut stack = Vec::with_capacity(2 * n);
18
19    stack.push((false, root, None));
20
21    while let Some((back, cur, par)) = stack.pop() {
22        if back {
23            let mut children = vec![];
24
25            for e in tree.nodes[cur].neighbors() {
26                if par.is_none_or(|p| p != e.to()) {
27                    children.push(ret[e.to()]);
28                }
29            }
30
31            children.sort_unstable();
32
33            let mut hasher = DefaultHasher::new();
34            children.hash(&mut hasher);
35            let h = hasher.finish();
36
37            let k = map.len();
38            ret[cur] = *map.entry(h).or_insert(k);
39        } else {
40            stack.push((true, cur, par));
41            for e in tree.nodes[cur].neighbors() {
42                if par.is_none_or(|p| p != e.to()) {
43                    stack.push((false, e.to(), Some(cur)));
44                }
45            }
46        }
47    }
48
49    (map.len(), ret)
50}
haar_lib/tree/rooted_isomorphism.rs

haar_lib/tree/
rooted_isomorphism.rs
