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)) }