Cod sursa(job #2671167)

Utilizator antonioganea3Antonio Ganea antonioganea3 Data 11 noiembrie 2020 16:40:14
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_N 1000001

using namespace std;

vector<int> links[MAX_N];
queue<int> q;

int n;
int contor[MAX_N];
int viz[MAX_N];
int last;
int diameter;

void BFS(int from){
    memset(contor,0,MAX_N);
    memset(viz,0,MAX_N);

    q.push(from);
    contor[from] = 1;

    viz[from] = 1;
    int i;
    int current;

    while( !q.empty() ){
        current = q.front();
        for( i=0; i < links[current].size(); i++ ){
            if( viz[links[current][i]] == 0 ){
                q.push(links[current][i]);
                contor[links[current][i]] = contor[current]+1;
                viz[links[current][i]] = 1;

                diameter = contor[links[current][i]];
                last = links[current][i];
            }
        }
        q.pop();
    }
}

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    fin >> n;

    int a, b;
    for ( int i = 0; i < n - 1; i++ ) {
        fin >> a >> b;
        links[a].push_back(b);
        links[b].push_back(a);
    }

    BFS(1);
    BFS(last);
    fout << diameter;
    return 0;

}