Doveqise

Doveqise

万事皆虚,诸行皆允

AT838 直径 题解

posted on 2019-05-08 21:45:30 | under 题解 |

这道题好像BFS是非正解来着QAQ
这里来一道BFS题解(良心BFS入门题)
觉得代码比较简明QwQ
细节下见代码↓

#include<bits/stdc++.h>
#define N 1005
using namespace std;
vector <int> vec[N][2];
int dist[N];
int bfs(int x,int p){
  queue <int> que;
  memset(dist,-1,sizeof(dist));
  dist[x]=0;que.push(x);int mx=0;
  while(!que.empty()){
    int v=que.front();que.pop();
    mx=dist[v];
    for(int i=0;i<vec[v][p].size();i++){
      int to=vec[v][p][i];
      if(dist[to]==-1){
        dist[to]=dist[v]+1;
        que.push(to);
      }
    }
  }
  return mx;
}
signed main(){
  int mn=1,mx=1;
  int rmn=0;
  for(int i=0;i<2;i++){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int j=0;j<m;j++){
      int a,b;scanf("%d %d",&a,&b);
      vec[a][i].push_back(b);
      vec[b][i].push_back(a);
    }
    int nmn=N,nmx=0;
    for(int j=0;j<n;j++){
      int vl=bfs(j,i);
      nmn=min(nmn,vl);
      nmx=max(nmx,vl);
    }
    mn+=nmn;mx+=nmx;
    rmn=max(rmn,nmx);
  }
  printf("%d %d\n",max(mn,rmn),mx);
  return 0;
}