Cod sursa(job #3210574)

Utilizator LittleProgrammerLittle Programmer LittleProgrammer Data 6 martie 2024 19:24:09
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;
const int N=100002;
int n,viz[N],q[N],pr,ul;
vector <int>L[N];

ifstream in("darb.in");
ofstream out("darb.out");
void citire(){
int i,x,y;
in>>n;

while(in>>x>>y){
    L[x].push_back(y);
    L[y].push_back(x);
}

}

void bfs(int x){
int i,xc,xv;
pr=ul=1;
viz[x]=1;
q[ul]=x;
while(pr<=ul){
    xc=q[pr++];
    for(i=0;i<L[xc].size();++i){
        xv=L[xc][i];
        if(!viz[xv]){
            viz[xv]=viz[xc]+1;
            q[++ul]=xv;
        }
    }
}

}

void rez(){
int i,max1=0,max2=0,nmax;
bfs(1);
for(i=1;i<=n;++i)
    if(viz[i]>max1){max1=viz[i];nmax=i;}

//cout<<nmax<<" "<<max1<<endl;
for(i=1;i<=n;++i)viz[i]=0;

bfs(nmax);
for(i=1;i<=n;++i){
    if(viz[i]>max2)max2=viz[i];
    viz[i]=0;
}

out<<max2;
}
int main(){
citire();
rez();
return 0;}