dsalgo/
farthest_node_on_unweighted_tree.rs

1use crate::{
2    argmax::argmax,
3    tree_bfs_parent_depth::bfs,
4};
5
6/// return (node, dist)
7
8pub fn farthest_node(
9    g: &[Vec<usize>],
10    u: usize,
11) -> (usize, usize) {
12    let (_, d) = bfs(g, u);
13
14    let v = argmax(&d);
15
16    (v, d[v])
17}
18
19#[cfg(test)]
20
21mod tests {
22
23    use super::*;
24
25    #[test]
26
27    fn test() {
28        let cases = vec![(
29            vec![
30                vec![1],
31                vec![0, 2],
32                vec![1, 3, 4],
33                vec![2],
34                vec![2, 5],
35                vec![4],
36            ],
37            0,
38            (5, 4),
39        )];
40
41        for (g, u, ans) in cases {
42            assert_eq!(farthest_node(&g, u), ans);
43        }
44    }
45}