competitive/tree/
tree_center.rs

1use crate::graph::UndirectedSparseGraph;
2
3#[codesnip::entry("tree_center")]
4#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
5pub enum TreeCenter {
6    One(usize),
7    Two(usize, usize),
8}
9#[codesnip::entry("tree_center", include("SparseGraph"))]
10impl UndirectedSparseGraph {
11    /// tree center
12    pub fn tree_center(&self) -> TreeCenter {
13        let n = self.vertices_size();
14        assert_ne!(n, 0);
15        let mut deq = std::collections::VecDeque::with_capacity(n);
16        let mut deg: Vec<_> = self.vertices().map(|u| self.adjacencies(u).len()).collect();
17        for u in self.vertices() {
18            if self.adjacencies(u).len() <= 1 {
19                deq.push_back(u);
20            }
21        }
22        let mut k = 0;
23        let mut cnt = deq.len();
24        if cnt < n {
25            k = deq.len();
26            'outer: while let Some(u) = deq.pop_front() {
27                k -= 1;
28                for a in self.adjacencies(u) {
29                    deg[a.to] -= 1;
30                    if deg[a.to] == 1 {
31                        deq.push_back(a.to);
32                        cnt += 1;
33                        if cnt == n {
34                            break 'outer;
35                        }
36                    }
37                }
38                if k == 0 {
39                    k = deq.len();
40                }
41            }
42        }
43        if deq.len() == k + 1 {
44            TreeCenter::One(*deq.back().unwrap())
45        } else {
46            let u = deq.pop_back().unwrap();
47            let v = deq.pop_back().unwrap();
48            if u < v {
49                TreeCenter::Two(u, v)
50            } else {
51                TreeCenter::Two(v, u)
52            }
53        }
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60    use crate::{graph::UndirectedSparseGraph, tools::Xorshift, tree::MixedTree};
61
62    impl UndirectedSparseGraph {
63        fn naive_tree_center(&self) -> TreeCenter {
64            let mut md: Vec<_> = self
65                .vertices()
66                .map(|u| (self.tree_depth(u).into_iter().max().unwrap_or_default(), u))
67                .collect();
68            md.sort_unstable();
69            if md.len() == 1 {
70                TreeCenter::One(md[0].1)
71            } else if md.len() >= 2 {
72                if md[0].0 == md[1].0 {
73                    TreeCenter::Two(md[0].1, md[1].1)
74                } else {
75                    TreeCenter::One(md[0].1)
76                }
77            } else {
78                panic!("vertex size should be larger than one.");
79            }
80        }
81    }
82
83    #[test]
84    fn test_center_handmaid() {
85        assert_eq!(
86            UndirectedSparseGraph::from_edges(1, vec![]).tree_center(),
87            TreeCenter::One(0)
88        );
89        assert_eq!(
90            UndirectedSparseGraph::from_edges(2, vec![(0, 1)]).tree_center(),
91            TreeCenter::Two(0, 1)
92        );
93        assert_eq!(
94            UndirectedSparseGraph::from_edges(3, vec![(0, 1), (0, 2)]).tree_center(),
95            TreeCenter::One(0)
96        );
97        assert_eq!(
98            UndirectedSparseGraph::from_edges(4, vec![(0, 1), (1, 2), (1, 3)]).tree_center(),
99            TreeCenter::One(1)
100        );
101        assert_eq!(
102            UndirectedSparseGraph::from_edges(5, vec![(0, 1), (1, 2), (1, 3), (3, 4)])
103                .tree_center(),
104            TreeCenter::Two(1, 3)
105        );
106        assert_eq!(
107            UndirectedSparseGraph::from_edges(
108                7,
109                vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
110            )
111            .tree_center(),
112            TreeCenter::One(3)
113        );
114    }
115
116    #[test]
117    fn test_center_random() {
118        let mut rng = Xorshift::default();
119        const N: usize = 200;
120        const Q: usize = 200;
121        for _ in 0..Q {
122            let n = rng.random(1..=N);
123            let g = rng.random(MixedTree(n));
124            assert_eq!(g.tree_center(), g.naive_tree_center());
125        }
126    }
127}
competitive/tree/tree_center.rs

competitive/tree/
tree_center.rs
