1use std::collections::VecDeque;
2
3pub fn from_root<T: Clone>(
4 n: usize,
5 es: &[(usize, usize, T)],
6 r: usize,
7) -> Vec<Vec<(usize, T)>> {
8 let mut g = vec![vec![]; n];
9 for &(u, v, ref w) in es {
10 g[u].push((v, w.clone()));
11 g[v].push((u, w.clone()));
12 }
13
14 let mut res = vec![vec![]; n];
15 let mut q = VecDeque::new();
16 let mut seen = vec![false; n];
17 q.push_back(r);
18 seen[r] = true;
19 while let Some(v) = q.pop_front() {
20 for (nv, nw) in g[v].drain(..) {
21 if seen[nv] {
22 continue;
23 }
24 seen[nv] = true;
25 res[v].push((nv, nw));
26 q.push_back(nv);
27 }
28 }
29 res
30}