competitive/graph/
order.rs

1use super::SparseGraph;
2
3#[codesnip::entry("bfs_order", include("SparseGraph"))]
4impl<D> SparseGraph<D> {
5    pub fn bfs_order(&self, root: usize) -> Vec<usize> {
6        let mut visited = vec![false; self.vertices_size()];
7        let mut ord = Vec::with_capacity(self.vertices_size());
8        visited[root] = true;
9        let mut deq = std::collections::VecDeque::new();
10        deq.push_back(root);
11        while let Some(u) = deq.pop_front() {
12            ord.push(u);
13            for a in self.adjacencies(u).rev() {
14                if !visited[a.to] {
15                    visited[a.to] = true;
16                    deq.push_back(a.to);
17                }
18            }
19        }
20        ord
21    }
22}
23
24#[codesnip::entry("dfs_order", include("SparseGraph"))]
25impl<D> SparseGraph<D> {
26    pub fn dfs_order(&self, root: usize) -> Vec<usize> {
27        let mut visited = vec![false; self.vertices_size()];
28        let mut ord = Vec::with_capacity(self.vertices_size());
29        visited[root] = true;
30        let mut stack = vec![root];
31        while let Some(u) = stack.pop() {
32            ord.push(u);
33            for a in self.adjacencies(u).rev() {
34                if !visited[a.to] {
35                    visited[a.to] = true;
36                    stack.push(a.to);
37                }
38            }
39        }
40        ord
41    }
42}
43
44#[codesnip::entry("dfs_tree", include("SparseGraph"))]
45impl<D> SparseGraph<D> {
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    }
62}
63
64#[codesnip::entry("for_each_connected_components", include("SparseGraph"))]
65impl<D> SparseGraph<D> {
66    /// f: |g, root, ord: [vertex, parent]| {}
67    pub fn for_each_connected_components<F>(&self, mut f: F)
68    where
69        F: FnMut(&Self, usize, &[(usize, usize)]),
70    {
71        let mut visited = vec![false; self.vertices_size()];
72        let mut ord = Vec::with_capacity(self.vertices_size());
73        for u in self.vertices() {
74            if !visited[u] {
75                visited[u] = true;
76                ord.push((u, !0));
77                let mut i = 0;
78                while i < ord.len() {
79                    let u = ord[i].0;
80                    for a in self.adjacencies(u).rev() {
81                        if !visited[a.to] {
82                            visited[a.to] = true;
83                            ord.push((a.to, u));
84                        }
85                    }
86                    i += 1;
87                }
88                f(self, u, &ord);
89                ord.clear();
90            }
91        }
92    }
93}
competitive/graph/order.rs

competitive/graph/
order.rs
