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
use crate::graph::{bfs::bfs, def::Graph, dfs::dfs};
use cargo_snippet::snippet;
#[snippet("bfs")]
pub fn dist_table<'a, G>(g: &'a G, start: G::NodeId) -> Vec<usize>
where
G: Graph<'a, NodeId = usize>,
{
let mut dist = vec![std::usize::MAX; g.len()];
dist[start] = 0;
for (f, t) in bfs(g, start) {
dist[t] = dist[f] + 1;
}
dist
}
#[snippet("bfs")]
pub fn shortest_path<'a, G: Graph<'a, NodeId = usize>>(
g: &'a G,
start: usize,
goal: usize,
) -> usize {
let mut dist = vec![std::usize::MAX; g.len()];
dist[start] = 0;
for (f, t) in bfs(g, start) {
if t == goal {
return dist[f] + 1;
}
dist[t] = dist[f] + 1;
}
std::usize::MAX
}
pub fn classify_into_connected_group<'a, G: Graph<'a, NodeId = usize>>(
g: &'a G,
) -> Vec<Vec<usize>> {
let mut classified = vec![None; g.len()];
let mut cur = 0usize;
for u in 0..g.len() {
match classified[u] {
Some(_) => {}
None => {
classified[u] = Some(cur);
for (_, t) in dfs(g, u) {
classified[t] = Some(cur);
}
cur += 1;
}
}
}
let mut res = vec![Vec::new(); cur];
for (i, c) in classified.into_iter().map(|x| x.unwrap()).enumerate() {
res[c].push(i);
}
res
}