Struct SparseGraph

Source

pub struct SparseGraph<D> {
    vsize: usize,
    pub start: Vec<usize>,
    pub elist: Vec<Adjacency>,
    pub edges: Vec<(usize, usize)>,
    _marker: PhantomData<fn() -> D>,
}

Expand description

Static Sparse Graph represented as Compressed Sparse Row.

Fields§

§vsize: usize§start: Vec<usize>§elist: Vec<Adjacency>§edges: Vec<(usize, usize)>§_marker: PhantomData<fn() -> D>

Implementations§

Source §

impl SparseGraph<DirectedEdge>

Source

pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
where N: Fn(usize) -> NA, E: Fn(usize) -> EA, NA: Display, EA: Display,

Source §

impl SparseGraph<UndirectedEdge>

Source

pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
where N: Fn(usize) -> NA, E: Fn(usize) -> EA, NA: Display, EA: Display,

Source §

impl SparseGraph<BidirectionalEdge>

Source

pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
where N: Fn(usize) -> NA, E: Fn(usize) -> EA, NA: Display, EA: Display,

Source §

pub fn for_each_connected_components<F>(&self, f: F)
where F: FnMut(&Self, usize, &[(usize, usize)]),

f: |g, root, ord: [vertex, parent]| {}

Source §

impl<D> SparseGraph<D>

Source

pub fn vertices_size(&self) -> usize

Return the number of vertices.

Examples found in repository ?

crates/competitive/src/graph/sparse_graph.rs (line 48)

47    pub fn vertices(&self) -> ops::Range<usize> {
48        0..self.vertices_size()
49    }

More examples

Hide additional examples

crates/competitive/src/tree/depth.rs (line 13)

12    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
13        let mut depth = vec![0; self.vertices_size()];
14        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
15        depth
16    }
17}
18
19#[codesnip::entry("weighted_tree_depth", include("algebra", "SparseGraph"))]
20impl UndirectedSparseGraph {
21    fn weighted_depth_dfs<M, F>(
22        &self,
23        u: usize,
24        p: usize,
25        d: M::T,
26        depth: &mut Vec<M::T>,
27        weight: &F,
28    ) where
29        M: Monoid,
30        F: Fn(usize) -> M::T,
31    {
32        for a in self.adjacencies(u).filter(|a| a.to != p) {
33            let nd = M::operate(&d, &weight(a.id));
34            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
35        }
36        depth[u] = d;
37    }
38    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
39        &self,
40        root: usize,
41        weight: F,
42    ) -> Vec<M::T> {
43        let mut depth = vec![M::unit(); self.vertices_size()];
44        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
45        depth
46    }
47}
48
49#[codesnip::entry("tree_size", include("SparseGraph"))]
50impl UndirectedSparseGraph {
51    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
52        size[u] = 1;
53        for a in self.adjacencies(u).filter(|a| a.to != p) {
54            self.size_dfs(a.to, u, size);
55            size[u] += size[a.to];
56        }
57    }
58    pub fn tree_size(&self, root: usize) -> Vec<u64> {
59        let mut size = vec![0; self.vertices_size()];
60        self.size_dfs(root, usize::MAX, &mut size);
61        size
62    }

crates/competitive/src/tree/euler_tour.rs (line 68)

67    pub fn new(tree: &'a UndirectedSparseGraph, root: usize) -> Self {
68        let n = tree.vertices_size();
69        Self {
70            tree,
71            root,
72            vidx: vec![[0usize; 2]; n],
73            eidx: vec![[0usize; 2]; n - 1],
74            pos: 0,
75            _marker: PhantomData,
76        }
77    }
78
79    pub fn build_with_trace(mut self, mut trace: impl FnMut(usize)) -> EulerTour<K> {
80        self.dfs(self.root, !0, &mut trace);
81        EulerTour {
82            root: self.root,
83            vidx: self.vidx,
84            eidx: self.eidx,
85            size: self.pos,
86            _marker: PhantomData,
87        }
88    }
89
90    pub fn build(self) -> EulerTour<K> {
91        self.build_with_trace(|_u| {})
92    }
93
94    fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize)) {
95        self.vidx[u][0] = self.pos;
96        trace(u);
97        self.pos += 1;
98        for a in self.tree.adjacencies(u) {
99            if a.to != parent {
100                self.eidx[a.id][0] = self.pos;
101                self.dfs(a.to, u, trace);
102                self.eidx[a.id][1] = self.pos;
103                if K::USE_VISIT {
104                    trace(u);
105                    self.pos += 1;
106                }
107            }
108        }
109        self.vidx[u][1] = self.pos;
110        if K::USE_LAST {
111            trace(u);
112            self.pos += 1;
113        }
114    }
115}
116
117impl EulerTourBuilder<'_, marker::First> {
118    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::First>, Vec<T>)
119    where
120        T: Clone,
121    {
122        assert_eq!(s.len(), self.tree.vertices_size());
123        let mut trace = Vec::with_capacity(marker::First::size(s.len()));
124        let tour = self.build_with_trace(|u| {
125            trace.push(s[u].clone());
126        });
127        (tour, trace)
128    }
129}
130
131impl EulerTourBuilder<'_, marker::FirstLast> {
132    pub fn build_with_rearrange<T>(
133        self,
134        s: &[T],
135        mut inverse: impl FnMut(T) -> T,
136    ) -> (EulerTour<marker::FirstLast>, Vec<T>)
137    where
138        T: Clone,
139    {
140        assert_eq!(s.len(), self.tree.vertices_size());
141        let mut visited = vec![false; s.len()];
142        let mut trace = Vec::with_capacity(marker::FirstLast::size(s.len()));
143        let tour = self.build_with_trace(|u| {
144            if !visited[u] {
145                trace.push(s[u].clone());
146                visited[u] = true;
147            } else {
148                trace.push(inverse(s[u].clone()));
149            }
150        });
151        (tour, trace)
152    }
153}
154
155impl EulerTourBuilder<'_, marker::Visit> {
156    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::Visit>, Vec<T>)
157    where
158        T: Clone,
159    {
160        assert_eq!(s.len(), self.tree.vertices_size());
161        let mut trace = Vec::with_capacity(marker::Visit::size(s.len()));
162        let tour = self.build_with_trace(|u| {
163            trace.push(s[u].clone());
164        });
165        (tour, trace)
166    }
167}
168
169impl UndirectedSparseGraph {
170    pub fn subtree_euler_tour_builder<'a>(
171        &'a self,
172        root: usize,
173    ) -> EulerTourBuilder<'a, marker::First> {
174        EulerTourBuilder::new(self, root)
175    }
176
177    pub fn path_euler_tour_builder<'a>(
178        &'a self,
179        root: usize,
180    ) -> EulerTourBuilder<'a, marker::FirstLast> {
181        EulerTourBuilder::new(self, root)
182    }
183
184    pub fn full_euler_tour_builder<'a>(
185        &'a self,
186        root: usize,
187    ) -> EulerTourBuilder<'a, marker::Visit> {
188        EulerTourBuilder::new(self, root)
189    }
190
191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let depth = self.tree_depth(root);
193        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
194        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
195        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
196            trace.push(u);
197            depth_trace.push(depth[u]);
198        });
199        let rmq = RangeMinimumQuery::new(depth_trace);
200        LowestCommonAncestor {
201            euler_tour,
202            trace,
203            rmq,
204        }
205    }

crates/competitive/src/tree/rerooting.rs (line 28)

27    pub fn new(graph: &'a UndirectedSparseGraph, rooting: F) -> Self {
28        let dp = vec![M::unit(); graph.vertices_size()];
29        let ep = vec![M::unit(); graph.vertices_size() * 2];
30        let mut self_ = Self {
31            graph,
32            dp,
33            ep,
34            rooting,
35        };
36        self_.rerooting();
37        self_
38    }

crates/competitive/src/tree/heavy_light_decomposition.rs (line 13)

11    pub fn new(root: usize, graph: &mut UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            par: vec![0; graph.vertices_size()],
14            size: vec![0; graph.vertices_size()],
15            head: vec![0; graph.vertices_size()],
16            vidx: vec![0; graph.vertices_size()],
17        };
18        self_.build(root, graph);
19        self_
20    }
21
22    fn dfs_size(&mut self, u: usize, p: usize, graph: &mut UndirectedSparseGraph) {
23        self.par[u] = p;
24        self.size[u] = 1;
25        let base = graph.start[u];
26        if graph.adjacencies(u).len() > 1 && graph.adjacencies(u).next().unwrap().to == p {
27            graph.elist.swap(base, base + 1);
28        }
29        for i in base..graph.start[u + 1] {
30            let a = graph.elist[i];
31            if a.to != p {
32                self.dfs_size(a.to, u, graph);
33                self.size[u] += self.size[a.to];
34                if self.size[graph.elist[base].to] < self.size[a.to] {
35                    graph.elist.swap(base, i);
36                }
37            }
38        }
39    }
40
41    fn dfs_hld(&mut self, u: usize, p: usize, t: &mut usize, graph: &UndirectedSparseGraph) {
42        self.vidx[u] = *t;
43        *t += 1;
44        let mut adjacencies = graph.adjacencies(u).filter(|a| a.to != p);
45        if let Some(a) = adjacencies.next() {
46            self.head[a.to] = self.head[u];
47            self.dfs_hld(a.to, u, t, graph);
48        }
49        for a in adjacencies {
50            self.head[a.to] = a.to;
51            self.dfs_hld(a.to, u, t, graph);
52        }
53    }
54
55    fn build(&mut self, root: usize, graph: &mut UndirectedSparseGraph) {
56        self.head[root] = root;
57        self.dfs_size(root, graph.vertices_size(), graph);
58        let mut t = 0;
59        self.dfs_hld(root, graph.vertices_size(), &mut t, graph);
60    }

crates/competitive/src/graph/low_link.rs (line 14)

11    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            graph,
14            low: vec![0; graph.vertices_size()],
15            ord: vec![usize::MAX; graph.vertices_size()],
16            articulation: vec![],
17            bridge: vec![],
18        };
19        for u in graph.vertices() {
20            if self_.ord[u] == usize::MAX {
21                self_.dfs(u, graph.vertices_size(), &mut 0);
22            }
23        }
24        self_
25    }
26    fn dfs(&mut self, u: usize, p: usize, now_ord: &mut usize) {
27        self.low[u] = *now_ord;
28        self.ord[u] = *now_ord;
29        *now_ord += 1;
30        let mut is_articulation = false;
31        let mut cnt = 0;
32        for a in self.graph.adjacencies(u) {
33            if self.ord[a.to] == usize::MAX {
34                cnt += 1;
35                self.dfs(a.to, u, now_ord);
36                self.low[u] = self.low[u].min(self.low[a.to]);
37                is_articulation |= p < self.graph.vertices_size() && self.ord[u] <= self.low[a.to];
38                if self.ord[u] < self.low[a.to] {
39                    self.bridge.push((u.min(a.to), u.max(a.to)));
40                }
41            } else if a.to != p {
42                self.low[u] = self.low[u].min(self.ord[a.to]);
43            }
44        }
45        is_articulation |= p == self.graph.vertices_size() && cnt > 1;
46        if is_articulation {
47            self.articulation.push(u);
48        }
49    }

Additional examples can be found in:

Source

pub fn edges_size(&self) -> usize

Return the number of edges.

Examples found in repository ?

crates/competitive/src/tree/rerooting.rs (line 41)

40    fn eidx(&self, u: usize, a: &Adjacency) -> usize {
41        a.id + self.graph.edges_size() * (u > a.to) as usize
42    }
43    #[inline]
44    fn reidx(&self, u: usize, a: &Adjacency) -> usize {
45        a.id + self.graph.edges_size() * (u < a.to) as usize
46    }

More examples

Hide additional examples

crates/competitive/src/graph/order.rs (line 48)

46    pub fn dfs_tree(&self, root: usize) -> Vec<bool> {
47        let mut visited = vec![false; self.vertices_size()];
48        let mut used = vec![false; self.edges_size()];
49        visited[root] = true;
50        let mut stack = vec![root];
51        while let Some(u) = stack.pop() {
52            for a in self.adjacencies(u).rev() {
53                if !visited[a.to] {
54                    visited[a.to] = true;
55                    used[a.id] = true;
56                    stack.push(a.to);
57                }
58            }
59        }
60        used
61    }

crates/competitive/src/tree/static_top_tree.rs (line 159)

155    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
156        let n = graph.vertices_size();
157        assert!(n > 0);
158        assert!(root < n);
159        assert_eq!(graph.edges_size() + 1, n);
160
161        let RootedInfo {
162            order,
163            children_start,
164            children,
165            edge_child,
166            parent_edge,
167        } = rooted_children(graph, root);
168        let mut this = Self {
169            root,
170            n,
171            edge_child,
172            parent_edge,
173            compressed: Vec::with_capacity(n.saturating_sub(1)),
174            raked: Vec::with_capacity(n.saturating_sub(1)),
175            vertex_links: vec![
176                VertexLinks {
177                    heavy_parent: usize::MAX,
178                    compress_parent: usize::MAX,
179                    rake_parent: usize::MAX,
180                };
181                n
182            ],
183            compress_roots: vec![None; n],
184            rake_roots: vec![None; n],
185        };
186
187        let mut heavy_child = vec![usize::MAX; n];
188        let mut mask = vec![1u64; n];
189        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());
190
191        for &u in order.iter().rev() {
192            let children = &children[children_start[u]..children_start[u + 1]];
193            let mut sum_rake = 0u64;
194            for &v in children {
195                sum_rake += bit_ceil(mask[v]) << 1;
196            }
197            mask[u] = bit_ceil(sum_rake);
198            for &v in children {
199                let child = bit_ceil(mask[v]) << 1;
200                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
201                let step = 1u64 << depth;
202                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
203                if cand <= mask[u] {
204                    mask[u] = cand;
205                    heavy_child[u] = v;
206                }
207            }
208
209            let mut has = 0u64;
210            let mut num_light = 0usize;
211            for &v in children {
212                if v == heavy_child[u] {
213                    continue;
214                }
215                num_light += 1;
216                let child = bit_ceil(mask[v]) << 1;
217                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
218                this.build_compress(v, &heavy_child, &mask);
219                buckets[depth].push(Node {
220                    depth,
221                    slot: Slot::RakeLeaf(v),
222                });
223                has |= 1u64 << depth;
224            }
225            if num_light == 0 {
226                continue;
227            }
228
229            while num_light > 1 {
230                let left = pop_bucket(&mut buckets, &mut has);
231                let right = pop_bucket(&mut buckets, &mut has);
232                let node = this.merge_rake(left, right);
233                let depth = node.depth;
234                buckets[depth].push(node);
235                has |= 1u64 << depth;
236                num_light -= 1;
237            }
238
239            let root = pop_bucket(&mut buckets, &mut has);
240            this.rake_roots[u] = Some(root.slot);
241            for &v0 in children {
242                if v0 == heavy_child[u] {
243                    continue;
244                }
245                let rake_parent = this.vertex_links[v0].rake_parent;
246                let mut v = v0;
247                while v != usize::MAX {
248                    this.vertex_links[v].heavy_parent = u;
249                    this.vertex_links[v].rake_parent = rake_parent;
250                    v = heavy_child[v];
251                }
252            }
253        }
254
255        this.build_compress(root, &heavy_child, &mask);
256        this
257    }
258
259    pub fn vertices_size(&self) -> usize {
260        self.n
261    }
262
263    pub fn edges_size(&self) -> usize {
264        self.edge_child.len()
265    }
266
267    pub fn dp<C>(
268        &self,
269        vertices: Vec<<C as Cluster>::Vertex>,
270        edges: Vec<<C as Cluster>::Edge>,
271    ) -> StaticTopTreeDp<'_, C>
272    where
273        C: Cluster,
274    {
275        StaticTopTreeDp::new(self, vertices, edges)
276    }
277
278    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
279        let start = vertex;
280        let mut stack = Vec::new();
281        while vertex != usize::MAX {
282            stack.push(Node {
283                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
284                slot: Slot::CompressLeaf(vertex),
285            });
286            loop {
287                let len = stack.len();
288                if len >= 3
289                    && (stack[len - 3].depth == stack[len - 2].depth
290                        || stack[len - 3].depth <= stack[len - 1].depth)
291                {
292                    let tail = stack.pop().unwrap();
293                    let right = stack.pop().unwrap();
294                    let left = stack.pop().unwrap();
295                    let node = self.merge_compress(left, right);
296                    stack.push(node);
297                    stack.push(tail);
298                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
299                    let right = stack.pop().unwrap();
300                    let left = stack.pop().unwrap();
301                    stack.push(self.merge_compress(left, right));
302                } else {
303                    break;
304                }
305            }
306            vertex = heavy_child[vertex];
307        }
308        while stack.len() > 1 {
309            let right = stack.pop().unwrap();
310            let left = stack.pop().unwrap();
311            stack.push(self.merge_compress(left, right));
312        }
313        let root = stack.pop().unwrap();
314        self.compress_roots[start] = Some(root.slot);
315        root
316    }
317
318    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
319        let id = self.compressed.len();
320        self.set_parent(left.slot, id << 1);
321        self.set_parent(right.slot, id << 1 | 1);
322        self.compressed.push(InnerNode {
323            left: left.slot,
324            right: right.slot,
325            parent: usize::MAX,
326        });
327        Node {
328            depth: left.depth.max(right.depth) + 1,
329            slot: Slot::CompressInner(id),
330        }
331    }
332
333    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
334        let id = self.raked.len();
335        self.set_parent(left.slot, id << 1);
336        self.set_parent(right.slot, id << 1 | 1);
337        self.raked.push(InnerNode {
338            left: left.slot,
339            right: right.slot,
340            parent: usize::MAX,
341        });
342        Node {
343            depth: left.depth.max(right.depth) + 1,
344            slot: Slot::RakeInner(id),
345        }
346    }
347
348    fn set_parent(&mut self, slot: Slot, parent: usize) {
349        match slot {
350            Slot::CompressLeaf(v) => self.vertex_links[v].compress_parent = parent,
351            Slot::CompressInner(i) => self.compressed[i].parent = parent,
352            Slot::RakeLeaf(v) => self.vertex_links[v].rake_parent = parent,
353            Slot::RakeInner(i) => self.raked[i].parent = parent,
354        }
355    }
356
357    fn init_compress<C>(
358        &self,
359        data: &mut StaticTopTreeDataBuilder<C>,
360        vertices: &[<C as Cluster>::Vertex],
361        edges: &[<C as Cluster>::Edge],
362        slot: Slot,
363    ) -> <C as Cluster>::Path
364    where
365        C: Cluster,
366    {
367        match slot {
368            Slot::CompressLeaf(vertex) => {
369                let point = self.init_point(data, vertices, edges, vertex);
370                C::add_vertex(
371                    &point,
372                    &vertices[vertex],
373                    self.parent_edge_ref(edges, vertex),
374                )
375            }
376            Slot::CompressInner(id) => {
377                let node = &self.compressed[id];
378                let left = self.init_compress(data, vertices, edges, node.left);
379                let right = self.init_compress(data, vertices, edges, node.right);
380                data.compressed[id].write(InnerValue {
381                    left: left.clone(),
382                    right: right.clone(),
383                });
384                C::compress(&left, &right)
385            }
386            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
387        }
388    }
389
390    fn init_point<C>(
391        &self,
392        data: &mut StaticTopTreeDataBuilder<C>,
393        vertices: &[<C as Cluster>::Vertex],
394        edges: &[<C as Cluster>::Edge],
395        vertex: usize,
396    ) -> <C as Cluster>::Point
397    where
398        C: Cluster,
399    {
400        let point = if let Some(slot) = self.rake_roots[vertex] {
401            self.init_rake(data, vertices, edges, slot)
402        } else {
403            C::unit_point()
404        };
405        data.light_points[vertex] = point.clone();
406        point
407    }
408
409    fn init_rake<C>(
410        &self,
411        data: &mut StaticTopTreeDataBuilder<C>,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Point
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::RakeLeaf(vertex) => {
421                let path = self.init_compress(
422                    data,
423                    vertices,
424                    edges,
425                    self.compress_roots[vertex].expect("light child path must exist"),
426                );
427                C::add_edge(&path)
428            }
429            Slot::RakeInner(id) => {
430                let node = &self.raked[id];
431                let left = self.init_rake(data, vertices, edges, node.left);
432                let right = self.init_rake(data, vertices, edges, node.right);
433                data.raked[id].write(InnerValue {
434                    left: left.clone(),
435                    right: right.clone(),
436                });
437                C::rake(&left, &right)
438            }
439            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
440        }
441    }
442
443    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
444        let edge = self.parent_edge[vertex];
445        if edge == usize::MAX {
446            None
447        } else {
448            Some(&edges[edge])
449        }
450    }
451}
452
453impl<'a, C> StaticTopTreeDp<'a, C>
454where
455    C: Cluster,
456{
457    pub fn new(
458        tree: &'a StaticTopTree,
459        vertices: Vec<<C as Cluster>::Vertex>,
460        edges: Vec<<C as Cluster>::Edge>,
461    ) -> Self {
462        assert_eq!(vertices.len(), tree.vertices_size());
463        assert_eq!(edges.len(), tree.edges_size());
464
465        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
466        let path = tree.init_compress(
467            &mut data,
468            &vertices,
469            &edges,
470            tree.compress_roots[tree.root].expect("root compress tree must exist"),
471        );
472        let all_point = C::add_edge(&path);
473        Self {
474            tree,
475            vertices,
476            edges,
477            compressed: unsafe { assume_init_vec(data.compressed) },
478            raked: unsafe { assume_init_vec(data.raked) },
479            light_points: data.light_points,
480            all_point,
481        }
482    }
483
484    pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex) {
485        assert!(vertex < self.vertices.len());
486        self.vertices[vertex] = value;
487        self.update_from_vertex(vertex);
488    }
489
490    pub fn set_edge(&mut self, edge: usize, value: <C as Cluster>::Edge) {
491        assert!(edge < self.edges.len());
492        self.edges[edge] = value;
493        self.update_from_vertex(self.tree.edge_child[edge]);
494    }
495
496    pub fn fold_all(&self) -> &<C as Cluster>::Point {
497        &self.all_point
498    }
499
500    pub fn fold_path(&self, mut vertex: usize) -> <C as Cluster>::Path {
501        assert!(vertex < self.tree.n);
502        let mut path = C::unit_path();
503        let mut point = self.light_points[vertex].clone();
504        loop {
505            let links = self.tree.vertex_links[vertex];
506            let mut left = C::unit_path();
507            let mut right = C::unit_path();
508            let mut compress_parent = links.compress_parent;
509            while compress_parent != usize::MAX {
510                let inner = &self.compressed[compress_parent / 2];
511                if compress_parent & 1 == 0 {
512                    right = C::compress(&right, &inner.right);
513                } else {
514                    left = C::compress(&inner.left, &left);
515                }
516                compress_parent = self.tree.compressed[compress_parent / 2].parent;
517            }
518            let right_point = C::add_edge(&right);
519            point = C::rake(&point, &right_point);
520            let mid = C::add_vertex(
521                &point,
522                &self.vertices[vertex],
523                self.tree.parent_edge_ref(&self.edges, vertex),
524            );
525            let mid = C::compress(&mid, &path);
526            path = C::compress(&left, &mid);
527            if links.heavy_parent == usize::MAX {
528                return path;
529            }
530
531            point = C::unit_point();
532            let mut rake_parent = links.rake_parent;
533            while rake_parent != usize::MAX {
534                let inner = &self.raked[rake_parent / 2];
535                if rake_parent & 1 == 0 {
536                    point = C::rake(&point, &inner.right);
537                } else {
538                    point = C::rake(&inner.left, &point);
539                }
540                rake_parent = self.tree.raked[rake_parent / 2].parent;
541            }
542            vertex = links.heavy_parent;
543        }
544    }
545
546    fn update_from_vertex(&mut self, mut vertex: usize) {
547        assert!(vertex < self.tree.n);
548        while vertex != usize::MAX {
549            let links = self.tree.vertex_links[vertex];
550            let base = C::add_vertex(
551                &self.light_points[vertex],
552                &self.vertices[vertex],
553                self.tree.parent_edge_ref(&self.edges, vertex),
554            );
555            let path = self.update_compress(links.compress_parent, base);
556            let point = C::add_edge(&path);
557            let point = self.update_rake(links.rake_parent, point);
558            if links.heavy_parent == usize::MAX {
559                self.all_point = point;
560            } else {
561                self.light_points[links.heavy_parent] = point;
562            }
563            vertex = links.heavy_parent;
564        }
565    }
566
567    fn update_compress(
568        &mut self,
569        mut id: usize,
570        mut path: <C as Cluster>::Path,
571    ) -> <C as Cluster>::Path {
572        while id != usize::MAX {
573            let inner = &mut self.compressed[id / 2];
574            if id & 1 == 0 {
575                inner.left = path;
576            } else {
577                inner.right = path;
578            }
579            path = C::compress(&inner.left, &inner.right);
580            id = self.tree.compressed[id / 2].parent;
581        }
582        path
583    }
584
585    fn update_rake(
586        &mut self,
587        mut id: usize,
588        mut point: <C as Cluster>::Point,
589    ) -> <C as Cluster>::Point {
590        while id != usize::MAX {
591            let inner = &mut self.raked[id / 2];
592            if id & 1 == 0 {
593                inner.left = point;
594            } else {
595                inner.right = point;
596            }
597            point = C::rake(&inner.left, &inner.right);
598            id = self.tree.raked[id / 2].parent;
599        }
600        point
601    }
602}
603
604struct StaticTopTreeDataBuilder<C>
605where
606    C: Cluster,
607{
608    compressed: Vec<MaybeUninit<InnerValue<<C as Cluster>::Path>>>,
609    raked: Vec<MaybeUninit<InnerValue<<C as Cluster>::Point>>>,
610    light_points: Vec<<C as Cluster>::Point>,
611}
612
613impl<C> StaticTopTreeDataBuilder<C>
614where
615    C: Cluster,
616{
617    fn new(tree: &StaticTopTree) -> Self {
618        let mut compressed = Vec::with_capacity(tree.compressed.len());
619        compressed.resize_with(tree.compressed.len(), MaybeUninit::uninit);
620        let mut raked = Vec::with_capacity(tree.raked.len());
621        raked.resize_with(tree.raked.len(), MaybeUninit::uninit);
622        Self {
623            compressed,
624            raked,
625            light_points: vec![C::unit_point(); tree.n],
626        }
627    }
628}
629
630unsafe fn assume_init_vec<T>(mut vec: Vec<MaybeUninit<T>>) -> Vec<T> {
631    let len = vec.len();
632    let cap = vec.capacity();
633    let ptr = vec.as_mut_ptr() as *mut T;
634    std::mem::forget(vec);
635    unsafe { Vec::from_raw_parts(ptr, len, cap) }
636}
637
638fn bit_ceil(x: u64) -> u64 {
639    if x <= 1 { 1 } else { x.next_power_of_two() }
640}
641
642fn rooted_children(graph: &UndirectedSparseGraph, root: usize) -> RootedInfo {
643    let n = graph.vertices_size();
644    let mut order = Vec::with_capacity(n);
645    let mut parent = vec![usize::MAX; n];
646    let mut parent_edge = vec![usize::MAX; n];
647    let mut edge_child = vec![0; graph.edges_size()];
648    order.push(root);
649    parent[root] = usize::MAX;
650    for i in 0..n {
651        let u = order[i];
652        for a in graph.adjacencies(u) {
653            if a.to == parent[u] {
654                continue;
655            }
656            parent[a.to] = u;
657            parent_edge[a.to] = a.id;
658            edge_child[a.id] = a.to;
659            order.push(a.to);
660        }
661    }
662    let mut children_start = vec![0usize; n + 1];
663    for &v in order.iter().skip(1) {
664        children_start[parent[v] + 1] += 1;
665    }
666    for i in 1..=n {
667        children_start[i] += children_start[i - 1];
668    }
669    let mut children = vec![0; n.saturating_sub(1)];
670    let mut child_pos = children_start.clone();
671    for &v in order.iter().skip(1) {
672        let pos = child_pos[parent[v]];
673        children[pos] = v;
674        child_pos[parent[v]] += 1;
675    }
676    RootedInfo {
677        order,
678        children_start,
679        children,
680        edge_child,
681        parent_edge,
682    }
683}

Source

pub fn vertices(&self) -> Range<usize>

Return an iterator over graph vertices.

Examples found in repository ?

crates/competitive/src/graph/low_link.rs (line 19)

11    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            graph,
14            low: vec![0; graph.vertices_size()],
15            ord: vec![usize::MAX; graph.vertices_size()],
16            articulation: vec![],
17            bridge: vec![],
18        };
19        for u in graph.vertices() {
20            if self_.ord[u] == usize::MAX {
21                self_.dfs(u, graph.vertices_size(), &mut 0);
22            }
23        }
24        self_
25    }

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_1_a.rs (line 14)

9pub fn grl_1_a(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
13    let cost = graph.standard_sp_additive().dijkstra([r], &d);
14    for u in graph.vertices() {
15        if cost[u].is_maximum() {
16            writeln!(writer, "INF").ok();
17        } else {
18            writeln!(writer, "{}", cost[u]).ok();
19        }
20    }
21}
22
23#[verify::aizu_online_judge("GRL_1_A")]
24pub fn grl_1_a_option(reader: impl Read, mut writer: impl Write) {
25    let s = read_all_unchecked(reader);
26    let mut scanner = Scanner::new(&s);
27    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
28    let cost = graph
29        .option_sp_additive()
30        .dijkstra([r], &|eid| Some(d[eid]));
31    for u in graph.vertices() {
32        match cost[u] {
33            Some(d) => writeln!(writer, "{}", d).ok(),
34            None => writeln!(writer, "INF").ok(),
35        };
36    }
37}

crates/competitive/src/graph/graphvis.rs (line 14)

5    pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
6    where
7        N: Fn(usize) -> NA,
8        E: Fn(usize) -> EA,
9        NA: Display,
10        EA: Display,
11    {
12        let mut s = String::new();
13        s.push_str("digraph G {\n    graph [ splines=false, layout=neato ];\n");
14        for u in self.vertices() {
15            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
16        }
17        for u in self.vertices() {
18            for a in self.adjacencies(u) {
19                writeln!(s, "    {} -> {} [{}];", u, a.to, edge_attr(a.id)).ok();
20            }
21        }
22        s.push('}');
23        s
24    }
25}
26
27impl UndirectedSparseGraph {
28    pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
29    where
30        N: Fn(usize) -> NA,
31        E: Fn(usize) -> EA,
32        NA: Display,
33        EA: Display,
34    {
35        let mut s = String::new();
36        s.push_str("graph G {\n    graph [ splines=false, layout=neato ];\n");
37        for u in self.vertices() {
38            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
39        }
40        for (i, (u, v)) in self.edges.iter().cloned().enumerate() {
41            writeln!(s, "    {} -- {} [{}];", u, v, edge_attr(i)).ok();
42        }
43        s.push('}');
44        s
45    }
46}
47
48impl BidirectionalSparseGraph {
49    pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
50    where
51        N: Fn(usize) -> NA,
52        E: Fn(usize) -> EA,
53        NA: Display,
54        EA: Display,
55    {
56        let mut s = String::new();
57        s.push_str("digraph G {\n    graph [ splines=false, layout=neato ];\n");
58        for u in self.vertices() {
59            writeln!(s, "    {} [{}];", u, node_attr(u)).ok();
60        }
61        for u in self.vertices() {
62            for a in self.adjacencies(u) {
63                writeln!(s, "    {} -> {} [{}];", u, a.to, edge_attr(a.id)).ok();
64            }
65        }
66        s.push('}');
67        s
68    }

crates/aizu_online_judge/src/grl/grl_1_b.rs (line 14)

6pub fn grl_1_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
10    let cost = graph
11        .option_sp_additive()
12        .bellman_ford([r], &|eid| Some(d[eid]), true);
13    if let Some(cost) = cost {
14        for u in graph.vertices() {
15            match cost[u] {
16                Some(d) => writeln!(writer, "{}", d).ok(),
17                None => writeln!(writer, "INF").ok(),
18            };
19        }
20    } else {
21        writeln!(writer, "NEGATIVE CYCLE").ok();
22    }
23}

crates/competitive/src/graph/strongly_connected_component.rs (line 29)

19    pub fn new(graph: &'a DirectedSparseGraph) -> Self {
20        let mut now_ord = 0;
21        let mut self_ = Self {
22            graph,
23            csize: 0,
24            visited: Vec::with_capacity(graph.vertices_size()),
25            low: vec![0; graph.vertices_size()],
26            ord: vec![usize::MAX; graph.vertices_size()],
27            comp: vec![0; graph.vertices_size()],
28        };
29        for u in graph.vertices() {
30            if self_.ord[u] == usize::MAX {
31                self_.dfs(u, &mut now_ord);
32            }
33        }
34        for x in self_.comp.iter_mut() {
35            *x = self_.csize - 1 - *x;
36        }
37        self_
38    }
39}
40impl StronglyConnectedComponent<'_> {
41    fn dfs(&mut self, u: usize, now_ord: &mut usize) {
42        self.low[u] = *now_ord;
43        self.ord[u] = *now_ord;
44        *now_ord += 1;
45        self.visited.push(u);
46        for a in self.graph.adjacencies(u) {
47            if self.ord[a.to] == usize::MAX {
48                self.dfs(a.to, now_ord);
49                self.low[u] = self.low[u].min(self.low[a.to]);
50            } else {
51                self.low[u] = self.low[u].min(self.ord[a.to]);
52            }
53        }
54        if self.low[u] == self.ord[u] {
55            while let Some(v) = self.visited.pop() {
56                self.ord[v] = self.graph.vertices_size();
57                self.comp[v] = self.csize;
58                if v == u {
59                    break;
60                }
61            }
62            self.csize += 1;
63        }
64    }
65    pub fn gen_cgraph(&self) -> DirectedSparseGraph {
66        let mut used = std::collections::HashSet::new();
67        let mut edges = vec![];
68        for u in self.graph.vertices() {
69            for a in self.graph.adjacencies(u) {
70                if self.comp[u] != self.comp[a.to] {
71                    let (x, y) = (self.comp[u], self.comp[a.to]);
72                    if !used.contains(&(x, y)) {
73                        used.insert((x, y));
74                        edges.push((x, y));
75                    }
76                }
77            }
78        }
79        DirectedSparseGraph::from_edges(self.size(), edges)
80    }
81    pub fn components(&self) -> Vec<Vec<usize>> {
82        let mut counts = vec![0; self.size()];
83        for &x in self.comp.iter() {
84            counts[x] += 1;
85        }
86        let mut groups = vec![vec![]; self.size()];
87        for (g, c) in groups.iter_mut().zip(counts) {
88            g.reserve(c);
89        }
90        for u in self.graph.vertices() {
91            groups[self[u]].push(u);
92        }
93        groups
94    }

crates/competitive/src/graph/topological_sort.rs (line 7)

4    pub fn topological_sort(&self) -> Vec<usize> {
5        let mut indeg = vec![0; self.vertices_size()];
6        let mut res = vec![];
7        for a in self.vertices().flat_map(|u| self.adjacencies(u)) {
8            indeg[a.to] += 1;
9        }
10        let mut stack = self
11            .vertices()
12            .filter(|&u| indeg[u] == 0)
13            .collect::<Vec<_>>();
14        while let Some(u) = stack.pop() {
15            res.push(u);
16            for a in self.adjacencies(u) {
17                indeg[a.to] -= 1;
18                if indeg[a.to] == 0 {
19                    stack.push(a.to);
20                }
21            }
22        }
23        res
24    }

Additional examples can be found in:

Source

pub fn adjacencies(&self, v: usize) -> Iter<'_, Adjacency>

Return a slice of adjacency vertices.

Examples found in repository ?

crates/competitive/src/tree/depth.rs (line 8)

6    fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>) {
7        depth[u] = d;
8        for a in self.adjacencies(u).filter(|a| a.to != p) {
9            self.depth_dfs(a.to, u, d + 1, depth);
10        }
11    }
12    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
13        let mut depth = vec![0; self.vertices_size()];
14        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
15        depth
16    }
17}
18
19#[codesnip::entry("weighted_tree_depth", include("algebra", "SparseGraph"))]
20impl UndirectedSparseGraph {
21    fn weighted_depth_dfs<M, F>(
22        &self,
23        u: usize,
24        p: usize,
25        d: M::T,
26        depth: &mut Vec<M::T>,
27        weight: &F,
28    ) where
29        M: Monoid,
30        F: Fn(usize) -> M::T,
31    {
32        for a in self.adjacencies(u).filter(|a| a.to != p) {
33            let nd = M::operate(&d, &weight(a.id));
34            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
35        }
36        depth[u] = d;
37    }
38    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
39        &self,
40        root: usize,
41        weight: F,
42    ) -> Vec<M::T> {
43        let mut depth = vec![M::unit(); self.vertices_size()];
44        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
45        depth
46    }
47}
48
49#[codesnip::entry("tree_size", include("SparseGraph"))]
50impl UndirectedSparseGraph {
51    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
52        size[u] = 1;
53        for a in self.adjacencies(u).filter(|a| a.to != p) {
54            self.size_dfs(a.to, u, size);
55            size[u] += size[a.to];
56        }
57    }

More examples

Hide additional examples

crates/competitive/src/tree/rerooting.rs (line 62)

59    fn dfs(&mut self, pa: &Adjacency, p: usize) {
60        let u = pa.to;
61        let pi = self.eidx(p, pa);
62        for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63            let i = self.eidx(u, a);
64            self.dfs(a, u);
65            self.ep[pi] = self.merge(&self.ep[pi], &self.ep[i]);
66        }
67        self.ep[pi] = self.add_subroot(&self.ep[pi], u, pa.id);
68    }
69    fn efs(&mut self, u: usize, p: usize) {
70        let m = self.graph.adjacencies(u).len();
71        let mut left = vec![M::unit(); m + 1];
72        let mut right = vec![M::unit(); m + 1];
73        for (k, a) in self.graph.adjacencies(u).enumerate() {
74            let i = self.eidx(u, a);
75            left[k + 1] = self.merge(&left[k], &self.ep[i]);
76        }
77        for (k, a) in self.graph.adjacencies(u).enumerate().rev() {
78            let i = self.eidx(u, a);
79            right[k] = self.merge(&right[k + 1], &self.ep[i]);
80        }
81        self.dp[u] = self.add_root(&left[m], u);
82        for (k, a) in self.graph.adjacencies(u).enumerate() {
83            if a.to != p {
84                let i = self.reidx(u, a);
85                self.ep[i] = self.merge(&left[k], &right[k + 1]);
86                self.ep[i] = self.add_subroot(&self.ep[i], u, a.id);
87                self.efs(a.to, u);
88            }
89        }
90    }
91    fn rerooting(&mut self) {
92        for a in self.graph.adjacencies(0) {
93            self.dfs(a, 0);
94        }
95        self.efs(0, usize::MAX);
96    }

crates/competitive/src/tree/tree_dp.rs (line 13)

9        fn dfs<T, F>(g: &UndirectedSparseGraph, u: usize, p: usize, dp: &mut [T], f: &mut F)
10        where
11            F: FnMut(&mut T, &T),
12        {
13            for a in g.adjacencies(u) {
14                if a.to != p {
15                    dfs(g, a.to, u, dp, f);
16                    assert_ne!(u, a.to);
17                    let ptr = dp.as_mut_ptr();
18                    unsafe { f(&mut *ptr.add(u), &*ptr.add(a.to)) };
19                }
20            }
21        }
22        dfs(self, root, !0, dp, &mut f);
23    }
24    pub fn tree_dp_top_down<T, F>(&self, root: usize, dp: &mut [T], mut f: F)
25    where
26        F: FnMut(&mut T, &T),
27    {
28        fn dfs<T, F>(g: &UndirectedSparseGraph, u: usize, p: usize, dp: &mut [T], f: &mut F)
29        where
30            F: FnMut(&mut T, &T),
31        {
32            for a in g.adjacencies(u) {
33                if a.to != p {
34                    assert_ne!(u, a.to);
35                    let ptr = dp.as_mut_ptr();
36                    unsafe { f(&mut *ptr.add(a.to), &*ptr.add(u)) };
37                    dfs(g, a.to, u, dp, f);
38                }
39            }
40        }

crates/competitive/src/tree/tree_hash.rs (line 66)

61    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
62        let mut s = 1u64;
63        if self.rv.len() <= d {
64            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
65        }
66        for a in g.adjacencies(u) {
67            if a.to != p {
68                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
69            }
70        }
71        s += self.rv[d];
72        if s >= Self::MOD {
73            s -= Self::MOD;
74        }
75        s
76    }

crates/competitive/src/tree/tree_order.rs (line 14)

6    pub fn tree_order(&self, root: usize) -> (Vec<usize>, Vec<usize>) {
7        let n = self.vertices_size();
8        let mut order = Vec::with_capacity(n);
9        let mut parents = vec![!0usize; n];
10        let mut stack = Vec::with_capacity(n);
11        stack.push(root);
12        while let Some(u) = stack.pop() {
13            order.push(u);
14            for a in self.adjacencies(u).rev() {
15                if a.to != parents[u] {
16                    parents[a.to] = u;
17                    stack.push(a.to);
18                }
19            }
20        }
21        (order, parents)
22    }

crates/competitive/src/tree/tree_centroid.rs (line 9)

5        fn dfs(g: &UndirectedSparseGraph, u: usize, p: usize) -> (usize, usize) {
6            let n = g.vertices_size();
7            let mut size = 1;
8            let mut ok = true;
9            for a in g.adjacencies(u) {
10                if a.to != p {
11                    let (s, c) = dfs(g, a.to, u);
12                    if c != !0 {
13                        return (0, c);
14                    }
15                    ok &= s * 2 <= n;
16                    size += s;
17                }
18            }
19            ok &= (n - size) * 2 <= n;
20            (size, if ok { u } else { !0 })
21        }

Additional examples can be found in:

Source

pub fn builder<T>(vsize: usize) -> SparseGraphBuilder<T, D>

Source

pub fn builder_with_esize<T>( vsize: usize, esize: usize, ) -> SparseGraphBuilder<T, D>

Source §

impl<D> SparseGraph<D>
where D: SparseGraphConstruction,

Source

pub fn from_edges(vsize: usize, edges: Vec<(usize, usize)>) -> Self

Construct graph from edges.

Examples found in repository ?

crates/competitive/src/graph/sparse_graph.rs (line 201)

200    pub fn build(self) -> (SparseGraph<D>, Vec<T>) {
201        let graph = SparseGraph::from_edges(self.vsize, self.edges);
202        (graph, self.rest)
203    }

More examples

Hide additional examples

crates/competitive/src/graph/maximum_flow.rs (line 32)

30    pub fn gen_graph(&mut self) -> BidirectionalSparseGraph {
31        let edges = std::mem::take(&mut self.edges);
32        BidirectionalSparseGraph::from_edges(self.vsize, edges)
33    }

crates/competitive/src/graph/minimum_cost_flow.rs (line 31)

29    pub fn gen_graph(&mut self) -> BidirectionalSparseGraph {
30        let edges = std::mem::take(&mut self.edges);
31        BidirectionalSparseGraph::from_edges(self.vsize, edges)
32    }

crates/competitive/src/tree/generator.rs (line 15)

7    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8        let n = rng.random(&self.0);
9        let edges = from_prufer_sequence(
10            n,
11            &rng.random_iter(0..n)
12                .take(n.saturating_sub(2))
13                .collect::<Vec<usize>>(),
14        );
15        UndirectedSparseGraph::from_edges(n, edges)
16    }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23        let n = rng.random(&self.0);
24        let edges = (1..n).map(|u| (u - 1, u)).collect();
25        UndirectedSparseGraph::from_edges(n, edges)
26    }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33        let n = rng.random(&self.0);
34        let edges = (1..n).map(|u| (0, u)).collect();
35        UndirectedSparseGraph::from_edges(n, edges)
36    }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }
69        let n = rng.random(&self.0);
70        let edges = rand_inner(n, rng);
71        UndirectedSparseGraph::from_edges(n, edges)
72    }

crates/competitive/src/graph/two_satisfiability.rs (line 34)

33    pub fn two_satisfiability(self) -> Option<Vec<bool>> {
34        let graph = DirectedSparseGraph::from_edges(self.vsize * 2, self.edges);
35        let scc = StronglyConnectedComponent::new(&graph);
36        let mut res = vec![false; self.vsize];
37        for i in 0..self.vsize {
38            if scc[i * 2] == scc[i * 2 + 1] {
39                return None;
40            }
41            res[i] = scc[i * 2] > scc[i * 2 + 1];
42        }
43        Some(res)
44    }

crates/library_checker/src/tree/lca.rs (line 11)

6pub fn lca_euler_tour(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, p: [usize]);
10    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
11    let tree = UndirectedSparseGraph::from_edges(n, edges);
12    let lca = tree.lca(0);
13    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
14        writeln!(writer, "{}", lca.lca(u, v)).ok();
15    }
16}
17
18#[verify::library_checker("lca")]
19pub fn lca_hld(reader: impl Read, mut writer: impl Write) {
20    let s = read_all_unchecked(reader);
21    let mut scanner = Scanner::new(&s);
22    scan!(scanner, n, q, p: [usize]);
23    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
24    let mut graph = UndirectedSparseGraph::from_edges(n, edges);
25    let hld = HeavyLightDecomposition::new(0, &mut graph);
26    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
27        writeln!(writer, "{}", hld.lca(u, v)).ok();
28    }
29}

Additional examples can be found in:

Source

pub fn reverse_graph(&self) -> SparseGraph<D>

Source §

impl<D> SparseGraph<D>

Source

pub fn topological_sort(&self) -> Vec<usize>

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_4_a.rs (line 10)

6pub fn grl_4_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, (graph, _): @DirectedGraphScanner::<usize, ()>::new(vs, es));
10    writeln!(writer, "{}", (graph.topological_sort().len() != vs) as u32).ok();
11}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_4_b.rs (line 10)

6pub fn grl_4_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, (graph, _): @DirectedGraphScanner::<usize, ()>::new(vs, es));
10    for u in graph.topological_sort().into_iter() {
11        writeln!(writer, "{}", u).ok();
12    }
13}

Source §

impl SparseGraph<UndirectedEdge>

Source

pub fn centroid_decomposition( &self, f: impl FnMut(&[usize], &[usize], usize, usize), )

1/3 centroid decomposition

f: (parents: &usize, vs: &usize, lsize: usize, rsize: usize)
0: root, 1..=lsize: left subtree, lsize+1..=lsize+rsize: right subtree

Examples found in repository ?

crates/competitive/src/tree/centroid_decomposition.rs (lines 374-399)

363    pub fn distance_frequencies(&self) -> Vec<u64> {
364        let n = self.vertices_size();
365        let mut table = vec![0u64; n];
366        if n == 0 {
367            return table;
368        }
369        table[0] = n as u64;
370        if n == 1 {
371            return table;
372        }
373        table[1] = (n * 2 - 2) as u64;
374        self.centroid_decomposition(|parents, vs, lsize, _rsize| {
375            let n = vs.len();
376            let mut dist = vec![0usize; n];
377            for i in 1..n {
378                dist[i] = dist[parents[i]] + 1;
379            }
380            let d_max = dist.iter().max().cloned().unwrap_or_default();
381            let mut f = vec![0u64; d_max + 1];
382            let mut g = vec![0u64; d_max + 1];
383            for i in 1..=lsize {
384                f[dist[i]] += 1;
385            }
386            for i in lsize + 1..n {
387                g[dist[i]] += 1;
388            }
389            while f.last().is_some_and(|&x| x == 0) {
390                f.pop();
391            }
392            while g.last().is_some_and(|&x| x == 0) {
393                g.pop();
394            }
395            let h = U64Convolve::convolve(f, g);
396            for (i, &x) in h.iter().enumerate() {
397                table[i] += x * 2;
398            }
399        });
400        table
401    }

Source

pub fn contour_query_range(&self) -> ContourQueryRange

Examples found in repository ?

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 20)

16pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);
22
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |start, end| {
28                    bit.update(start, x);
29                    bit.update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |i| ans += bit.accumulate(i));
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

More examples

Hide additional examples

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 20)

16pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut raw = vec![0; cq.len()];
22    for (v, &x) in a.iter().enumerate() {
23        cq.for_each_index(v, |i| raw[i] += x);
24    }
25    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
26    for _ in 0..q {
27        scan!(scanner, query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |i| bit.update(i, x));
32            }
33            Query::Sum { v, l, r } => {
34                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
35                cq.for_each_contour_range(v, l, r, |start, end| {
36                    ans += bit.fold(start, end);
37                });
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

Source

pub fn distance_frequencies(&self) -> Vec<u64>

Examples found in repository ?

crates/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 10)

6pub fn frequency_table_of_tree_distance(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let freqs = g.distance_frequencies();
11    iter_print!(writer, @it freqs[1..].iter().map(|&f| f / 2));
12}

Source §

impl SparseGraph<UndirectedEdge>

Source

fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>)

Examples found in repository ?

crates/competitive/src/tree/depth.rs (line 9)

6    fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>) {
7        depth[u] = d;
8        for a in self.adjacencies(u).filter(|a| a.to != p) {
9            self.depth_dfs(a.to, u, d + 1, depth);
10        }
11    }
12    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
13        let mut depth = vec![0; self.vertices_size()];
14        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
15        depth
16    }

Source

pub fn tree_depth(&self, root: usize) -> Vec<u64>

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 192)

191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let depth = self.tree_depth(root);
193        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
194        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
195        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
196            trace.push(u);
197            depth_trace.push(depth[u]);
198        });
199        let rmq = RangeMinimumQuery::new(depth_trace);
200        LowestCommonAncestor {
201            euler_tour,
202            trace,
203            rmq,
204        }
205    }

More examples

Hide additional examples

crates/library_checker/src/tree/jump_on_tree.rs (line 34)

29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}

Source §

impl SparseGraph<UndirectedEdge>

Source

fn weighted_depth_dfs<M, F>( &self, u: usize, p: usize, d: M::T, depth: &mut Vec<M::T>, weight: &F, )
where M: Monoid, F: Fn(usize) -> M::T,

Examples found in repository ?

crates/competitive/src/tree/depth.rs (line 34)

21    fn weighted_depth_dfs<M, F>(
22        &self,
23        u: usize,
24        p: usize,
25        d: M::T,
26        depth: &mut Vec<M::T>,
27        weight: &F,
28    ) where
29        M: Monoid,
30        F: Fn(usize) -> M::T,
31    {
32        for a in self.adjacencies(u).filter(|a| a.to != p) {
33            let nd = M::operate(&d, &weight(a.id));
34            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
35        }
36        depth[u] = d;
37    }
38    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
39        &self,
40        root: usize,
41        weight: F,
42    ) -> Vec<M::T> {
43        let mut depth = vec![M::unit(); self.vertices_size()];
44        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
45        depth
46    }

Source

pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>( &self, root: usize, weight: F, ) -> Vec<M::T>

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_a.rs (line 10)

6pub fn grl_5_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
10    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
11    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
12    let ans = graph
13        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
14        .into_iter()
15        .max()
16        .unwrap();
17    writeln!(writer, "{}", ans).ok();
18}

Source §

impl SparseGraph<UndirectedEdge>

Source

fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>)

Examples found in repository ?

crates/competitive/src/tree/depth.rs (line 54)

51    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
52        size[u] = 1;
53        for a in self.adjacencies(u).filter(|a| a.to != p) {
54            self.size_dfs(a.to, u, size);
55            size[u] += size[a.to];
56        }
57    }
58    pub fn tree_size(&self, root: usize) -> Vec<u64> {
59        let mut size = vec![0; self.vertices_size()];
60        self.size_dfs(root, usize::MAX, &mut size);
61        size
62    }

Source

pub fn tree_size(&self, root: usize) -> Vec<u64>

Source §

impl SparseGraph<UndirectedEdge>

Source

pub fn subtree_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, First>

Examples found in repository ?

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 21)

15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

Source

pub fn path_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, FirstLast>

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 26)

16pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, c: [SizedCollect<usize>]);
20    let edges = c
21        .take(n)
22        .enumerate()
23        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
24        .collect();
25    let graph = UndirectedSparseGraph::from_edges(n, edges);
26    let et = graph.path_euler_tour_builder(0).build();
27    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
28
29    scan!(scanner, q);
30    for _ in 0..q {
31        scan!(scanner, query: Query);
32        match query {
33            Query::Add { v, w } => {
34                et.update(v, w, -w, |k, x| bit.update(k, x));
35            }
36            Query::Get { u } => {
37                let ans = et.fold(u, |k| bit.accumulate(k));
38                writeln!(writer, "{}", ans).ok();
39            }
40        }
41    }
42}

Source

pub fn full_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, Visit>

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 195)

191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let depth = self.tree_depth(root);
193        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
194        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
195        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
196            trace.push(u);
197            depth_trace.push(depth[u]);
198        });
199        let rmq = RangeMinimumQuery::new(depth_trace);
200        LowestCommonAncestor {
201            euler_tour,
202            trace,
203            rmq,
204        }
205    }

Source

pub fn lca(&self, root: usize) -> LowestCommonAncestor

Examples found in repository ?

crates/library_checker/src/tree/lca.rs (line 12)

6pub fn lca_euler_tour(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, p: [usize]);
10    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
11    let tree = UndirectedSparseGraph::from_edges(n, edges);
12    let lca = tree.lca(0);
13    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
14        writeln!(writer, "{}", lca.lca(u, v)).ok();
15    }
16}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_5_c.rs (line 16)

6pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, c: [SizedCollect<usize>]);
10    let edges = c
11        .take(n)
12        .enumerate()
13        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
14        .collect();
15    let tree = UndirectedSparseGraph::from_edges(n, edges);
16    let lca = tree.lca(0);
17    scan!(scanner, q, uv: [(usize, usize)]);
18    for (u, v) in uv.take(q) {
19        writeln!(writer, "{}", lca.lca(u, v)).ok();
20    }
21}

crates/library_checker/src/tree/jump_on_tree.rs (line 11)

6pub fn jump_on_tree(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let la = g.level_ancestor(0);
11    let lca = g.lca(0);
12    for _ in 0..q {
13        scan!(scanner, s, t, i);
14        let l = lca.lca(s, t);
15        let ds = la.depth(s) - la.depth(l);
16        let dt = la.depth(t) - la.depth(l);
17        let ans = if i <= ds {
18            la.la(s, i)
19        } else if i <= ds + dt {
20            la.la(t, ds + dt - i)
21        } else {
22            None
23        };
24        writeln!(writer, "{}", ans.unwrap_or(!0) as isize).ok();
25    }
26}
27
28#[verify::library_checker("jump_on_tree")]
29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}

Source §

impl SparseGraph<UndirectedEdge>

Source

pub fn level_ancestor(&self, root: usize) -> LevelAncestor

Examples found in repository ?

crates/library_checker/src/tree/jump_on_tree.rs (line 10)

6pub fn jump_on_tree(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let la = g.level_ancestor(0);
11    let lca = g.lca(0);
12    for _ in 0..q {
13        scan!(scanner, s, t, i);
14        let l = lca.lca(s, t);
15        let ds = la.depth(s) - la.depth(l);
16        let dt = la.depth(t) - la.depth(l);
17        let ans = if i <= ds {
18            la.la(s, i)
19        } else if i <= ds + dt {
20            la.la(t, ds + dt - i)
21        } else {
22            None
23        };
24        writeln!(writer, "{}", ans.unwrap_or(!0) as isize).ok();
25    }
26}

More examples

Hide additional examples

crates/competitive/src/algorithm/doubling.rs (line 278)

183    pub fn new(size: usize, f: impl Fn(usize) -> (usize, M::T)) -> Self {
184        let (next, value): (Vec<_>, Vec<_>) = (0..size).map(f).unzip();
185
186        let mut indeg = vec![0usize; size];
187        for &to in &next {
188            indeg[to] += 1;
189        }
190        let mut in_cycle = vec![true; size];
191        let mut deq = VecDeque::new();
192        for (u, &deg) in indeg.iter().enumerate() {
193            if deg == 0 {
194                deq.push_back(u);
195            }
196        }
197        while let Some(u) = deq.pop_front() {
198            in_cycle[u] = false;
199            indeg[next[u]] -= 1;
200            if indeg[next[u]] == 0 {
201                deq.push_back(next[u]);
202            }
203        }
204
205        let mut cycle_id = vec![!0; size];
206        let mut cycle_pos = vec![!0; size];
207        let mut cycles = Vec::new();
208        for i in 0..size {
209            if in_cycle[i] && cycle_id[i] == !0 {
210                let mut cycle = Vec::new();
211                let mut u = i;
212                loop {
213                    cycle_id[u] = cycles.len();
214                    cycle_pos[u] = cycle.len();
215                    cycle.push(u);
216                    u = next[u];
217                    if u == i {
218                        break;
219                    }
220                }
221                cycles.push(cycle);
222            }
223        }
224
225        let mut rev = vec![Vec::new(); size];
226        for u in 0..size {
227            rev[next[u]].push(u);
228        }
229
230        let mut depth_to_cycle = vec![0usize; size];
231        let mut cycle_entry = vec![!0; size];
232        let mut prefix_up = Vec::with_capacity(size);
233        prefix_up.resize_with(size, M::unit);
234        let mut q = VecDeque::new();
235        for i in 0..size {
236            if in_cycle[i] {
237                cycle_entry[i] = i;
238                prefix_up[i] = M::operate(&value[i], &M::unit());
239                q.push_back(i);
240            }
241        }
242        while let Some(u) = q.pop_front() {
243            for &v in &rev[u] {
244                if in_cycle[v] || cycle_entry[v] != !0 {
245                    continue;
246                }
247                cycle_entry[v] = cycle_entry[u];
248                depth_to_cycle[v] = depth_to_cycle[u] + 1;
249                cycle_id[v] = cycle_id[u];
250                prefix_up[v] = M::operate(&value[v], &prefix_up[u]);
251                q.push_back(v);
252            }
253        }
254
255        let mut cycle_prefix = Vec::with_capacity(cycles.len());
256        for cycle in &cycles {
257            let len = cycle.len();
258            let mut pref = Vec::with_capacity(2 * len + 1);
259            pref.push(M::unit());
260            for i in 0..2 * len {
261                let v = cycle[i % len];
262                let next_val = M::operate(pref.last().unwrap(), &value[v]);
263                pref.push(next_val);
264            }
265            cycle_prefix.push(pref);
266        }
267
268        let root = size;
269        let mut edges = Vec::with_capacity(size);
270        for u in 0..size {
271            if in_cycle[u] {
272                edges.push((u, root));
273            } else {
274                edges.push((u, next[u]));
275            }
276        }
277        let graph = UndirectedSparseGraph::from_edges(size + 1, edges);
278        let la = graph.level_ancestor(root);
279
280        Self {
281            depth_to_cycle,
282            cycle_entry,
283            cycle_id,
284            cycle_pos,
285            cycles,
286            cycle_prefix,
287            prefix_up,
288            la,
289        }
290    }

Source

pub fn level_ancestor_batch( &self, root: usize, queries: impl IntoIterator<Item = (usize, usize)>, ) -> Vec<Option<usize>>

Examples found in repository ?

crates/library_checker/src/tree/jump_on_tree.rs (lines 35-49)

29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}

Source §

impl SparseGraph<UndirectedEdge>

Source

pub fn static_top_tree(&self, root: usize) -> StaticTopTree

Examples found in repository ?

crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 117)

106pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, mut writer: impl Write) {
107    let s = read_all_unchecked(reader);
108    let mut scanner = Scanner::new(&s);
109    scan!(
110        scanner,
111        n,
112        q,
113        value: [MInt; n],
114        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
115    );
116
117    let top_tree = graph.static_top_tree(0);
118    let mut dp = top_tree.dp::<Dp>(value, edges);
119
120    for _ in 0..q {
121        scan!(scanner, query: Query);
122        match query {
123            Query::SetVertex { v, x } => {
124                dp.set_vertex(v, x);
125                writeln!(writer, "{}", dp.fold_all().sum).ok();
126            }
127            Query::SetEdge { e, a, b } => {
128                dp.set_edge(e, (a, b));
129                writeln!(writer, "{}", dp.fold_all().sum).ok();
130            }
131        }
132    }
133}

More examples

Hide additional examples

crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 151)

140pub fn point_set_tree_path_composite_sum(reader: impl Read, mut writer: impl Write) {
141    let s = read_all_unchecked(reader);
142    let mut scanner = Scanner::new(&s);
143    scan!(
144        scanner,
145        n,
146        q,
147        value: [MInt; n],
148        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
149    );
150
151    let top_tree = graph.static_top_tree(0);
152    let mut dp = top_tree.dp::<Dp>(value, edges);
153
154    for _ in 0..q {
155        scan!(scanner, query: Query);
156        match query {
157            Query::SetVertex { v, x, r } => {
158                dp.set_vertex(v, x);
159                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
160            }
161            Query::SetEdge { e, a, b, r } => {
162                dp.set_edge(e, (a, b));
163                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
164            }
165        }
166    }
167}

Source §

impl SparseGraph<UndirectedEdge>

Source

pub fn tree_center(&self) -> TreeCenter

tree center

Examples found in repository ?

crates/competitive/src/tree/tree_hash.rs (line 51)

50    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
51        match g.tree_center() {
52            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
53            TreeCenter::Two(u, v) => {
54                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
55            }
56        }
57    }