AtCoder Beginner Contest 309 D

https://atcoder.jp/contests/abc309/tasks/abc309_d

2つグラフを作って、それぞれ最長距離を求めます。

// Add One Edge
#![allow(non_snake_case)]

use std::collections::VecDeque;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);
type Graph = Vec<Vec<Node>>;

fn read_edge() -> Edge {
    let v: Vec<Node> = read_vec();
    (v[0]-1, v[1]-1)
}

fn create_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph = vec![vec![]; N];
    for (u, v) in edges.into_iter() {
        graph[u].push(v);
        graph[v].push(u)
    }
    graph
}


//////////////////// process ////////////////////

fn read_input() -> (usize, usize, Vec<Edge>) {
    let v = read_vec();
    let N1 = v[0];
    let N2 = v[1];
    let M = v[2];
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    (N1, N2, edges)
}

fn farthest_distance(graph: &Graph, v0: Node) -> i32 {
    let N = graph.len();
    let mut dists: Vec<i32> = vec![-1; N];
    let mut q = VecDeque::new();
    dists[v0] = 0;
    q.push_back(v0);
    while let Some(v) = q.pop_front() {
        let d = dists[v];
        for &u in graph[v].iter() {
            if dists[u] == -1 {
                dists[u] = d + 1;
                q.push_back(u)
            }
        }
    }
    dists.into_iter().max().unwrap()
}

fn f(N1: usize, N2: usize, edges: Vec<Edge>) -> i32 {
    let edges1: Vec<Edge> = edges.iter().filter(|&e| e.0 < N1).
                                            map(|&e| e).collect();
    let edges2: Vec<Edge> = edges.iter().filter(|&e| e.0 >= N1).
                                map(|&(u, v)| (u-N1, v-N1)).collect();
    let graph1 = create_graph(N1, edges1);
    let graph2 = create_graph(N2, edges2);
    farthest_distance(&graph1, 0) + farthest_distance(&graph2, N2-1) + 1
}


//////////////////// main ////////////////////

fn main() {
    let (N1, N2, edges) = read_input();
    println!("{}", f(N1, N2, edges))
}