Cod sursa(job #2215487)

Utilizator NashikAndrei Feodorov Nashik Data 22 iunie 2018 12:58:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

FILE *in,*out;

//constante
const int Nmax = (int) 1e5+1;
const int oo = 0x3f3f3f3f;


int n,nod1,nod2;
vector<int> graf[Nmax];
int first=1,last;
int dist;
int distanta[Nmax];
void bfs(int node)
{
    queue<int> q;
    q.push(node);
    memset(distanta,oo,sizeof(distanta));
    distanta[node]=0;
    dist=0;

    while(!q.empty())
    {
        int curent = q.front();
        q.pop();

        vector<int> :: iterator it,end=graf[curent].end();
        for(it=graf[curent].begin() ; it!=end ; ++it){
            if(distanta[*it]==oo){
                q.push(*it);
                distanta[*it]=distanta[curent]+1;
                if(dist<distanta[*it]){
                    dist=distanta[*it];
                    last=*it;
                }
            }
        }
    }
}
int main()
{
    in = fopen("darb.in" , "rt");
    out = fopen("darb.out" , "wt");
    fscanf(in,"%d", &n);
    for(int i=1 ; i<n ; ++i){
        fscanf(in, "%d%d",&nod1,&nod2);
        graf[nod1].push_back(nod2);
        graf[nod2].push_back(nod1);
    }
    bfs(first);
    bfs(last);
    fprintf(out,"%d\n",dist+1);
    fclose(in);
    fclose(out);
    return 0;
}