Cod sursa(job #2259315)

Utilizator TavinciStefanescu Octavian Tavinci Data 13 octombrie 2018 11:29:52
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define NMAX 1000001

using namespace std;

vector<int> G[NMAX];

queue<int> coada;

int n, m, viz[NMAX], comp, cost[NMAX], maxim=0, lungime, nod2;
ifstream fin("darb.in");
ofstream fout("darb.out");


void bfs(int plecare){
    memset(cost,0,NMAX);
    memset(viz,0,NMAX);
    coada.push(plecare);
    cost[plecare]=1;
    viz[plecare]=1;
    int actualNod;
    while(!coada.empty()){
        actualNod=coada.front();
        for(int i=0;i<G[actualNod].size();i++){
            if(viz[G[actualNod][i]]==0){
                coada.push(G[actualNod][i]);
                cost[G[actualNod][i]]=cost[actualNod]+1;
                viz[G[actualNod][i]]=1;
                lungime=cost[G[actualNod][i]];
                nod2=G[actualNod][i];
            }
        }
        coada.pop();
    }
}

int main()
{
    fin>>n;
    int p1, p2;
    for(int i=1; i<=n-1; i++)
    {
        fin>>p1>>p2;
        G[p1].push_back(p2);
        G[p2].push_back(p1);
    }

    bfs(1);
    bfs(nod2);
    fout<<lungime;
    return 0;
}