Cod sursa(job #2671897)

Utilizator antonioganea3Antonio Ganea antonioganea3 Data 12 noiembrie 2020 19:47:33
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

#define MAX_N 1000001

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

int n;
int contor[MAX_N];
int visited[MAX_N];
int last;

void BFS(int from){
    q.push(from);
    contor[from] = 1;

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

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

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

int visited2[MAX_N];
int answer = 0;
void dfs( int node, int dist ) {
    visited2[node] = 1;
    if ( dist > answer )
        answer = dist;

    for ( auto &x : links[node] ){
        if ( visited2[x] == 0)
            dfs(x, dist+1);
    }
}

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);
    dfs(last,1);
    fout << answer;
    return 0;

}