AtCoder Beginner Contest 309D

ABC309D

Connected component 毎に，始点を固定したときの最短距離はBFSで求まる． つまり，その中での最大値も求まる．
2つの connected component それぞれの最大値を求めて， それの和 + 1 が答え．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n0, n1, m;

  cin >> n0 >> n1 >> m;

 

  vvll to(n0+n1);

  rep(i,m){

    ll a, b; cin >> a >> b;

    --a, --b;

    to[a].push_back(b);

    to[b].push_back(a);

  }

  auto bfs = [&](ll src) -> vll {

    vll dis(n0+n1, INFL);

    vector<bool> vis(n0+n1);

    queue<ll> que;

    auto push = [&](ll v, ll d) -> void {

      if(vis[v]) return;

      vis[v] = true;

      que.push(v);

      dis[v] = d;

    };

    push(src, 0);

    while(que.size()){

      ll cu = que.front(); que.pop();

      ll d = dis[cu];

      for(auto ne: to[cu]){

        push(ne, d + 1);

      }

    }

    return dis;

  };

  vll d0 = bfs(0);

  vll d1 = bfs(n0+n1-1);

  ll m0 = -INFL;

  ll m1 = -INFL;

  for(auto i: d0){

    if(i < INFL) chmax(m0, i);

  }

  for(auto i: d1){

    if(i < INFL) chmax(m1, i);

  }

  cout << m0 + m1 + 1 << endl;

  return 0;

}