Cod sursa(job #2648327)

Utilizator LeCapataIustinian Serban LeCapata Data 10 septembrie 2020 12:03:11
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define N 100001
using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

int n, ultim, contor[N], diametru;
bool fol[N];
vector< vector<int> > muchii(N);
queue<int> coada;

void dfs(int nod){
    memset(contor, 0, N);
    memset(fol, 0, N);

    coada.push(nod);
    fol[nod] = 1;
    contor[nod] = 1;

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

        for(size_t i = 0; i < muchii[curent].size(); ++i)
            if(!fol[muchii[curent][i]]){
                coada.push(muchii[curent][i]);
                fol[muchii[curent][i]] = 1;
                contor[muchii[curent][i]] = contor[curent] + 1;

                diametru = contor[muchii[curent][i]];
                ultim = muchii[curent][i];
            }
    }
}
int main()
{
    in>>n;

    for(int i = 1; i < n; ++i){
        int x, y;
        in>>x>>y;

        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    dfs(1);
    dfs(ultim);

    out<<diametru;
    in.close();
    out.close();
    return 0;
}