Cod sursa(job #2455936)

Utilizator AlexandruPaulSirbu Alex AlexandruPaul Data 13 septembrie 2019 09:44:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
const int Maxx=1e5+1;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int>A[Maxx];
vector <int>::iterator it;
queue <int> Q;
bool vis[Maxx];
int dist[Maxx];
int n;
int mx;
int x,y,ac,node;
void bfs(int start){
    mx=0;
    for (int i=1;i<=n;++i) vis[i]=0;
    Q.push(start);
    dist[start]=1;
    vis[start]=1;
    while (!Q.empty()){
        ac=Q.front();
        Q.pop();
        for (it=A[ac].begin();it!=A[ac].end();++it){
            if (!vis[(*it)]){
                vis[(*it)]=1;
                dist[(*it)]=dist[ac]+1;
                if (dist[(*it)]>mx){
                    mx=dist[(*it)];
                    node=(*it);
                }
                Q.push((*it));
            }
        }
    }
}
int main(){
    fin>>n;
    for (;fin>>x>>y;){
        A[x].push_back(y);
        A[y].push_back(x);
    }
    bfs(1);
    bfs(node);
    fout<<mx;
    return 0;
}