Cod sursa(job #2216129)

Utilizator HumikoPostu Alexandru Humiko Data 25 iunie 2018 13:46:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define oo 1e8

using namespace std;

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

int n, diameter, last_Node;
int dist[NMAX];
vector <int> graph[NMAX];

void bfs( int starting_Point )
{
    queue <int> list_of_Nodes;
    list_of_Nodes.push(starting_Point);
    for ( int i = 1; i <= n; ++i )
        dist[i] = oo;
    dist[starting_Point] = 1;
    while ( list_of_Nodes.size() )
    {
        int current_Node = list_of_Nodes.front();
        list_of_Nodes.pop();
        for ( auto x:graph[current_Node] )
        {
            if ( dist[x] == oo )
            {
                dist[x] = dist[current_Node]+1;
                if ( dist[x] > diameter )
                {
                    diameter = dist[x];
                    last_Node = x;
                }
                list_of_Nodes.push(x);
            }
        }
    }
}

int main()
{
    fin>>n;
    for ( int i = 1; i <= n; ++i )
    {
        int first_Node, second_Node;
        fin>>first_Node>>second_Node;
        graph[first_Node].push_back(second_Node);
        graph[second_Node].push_back(first_Node);
    }
    bfs(1);
    bfs(last_Node);
    fout<<diameter<<'\n';
}