Cod sursa(job #2148827)

Utilizator antracodsAntracod antracods Data 2 martie 2018 02:24:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 100003;

vector <int> Graf[NMAX];
queue <int> my_queue;

int road[NMAX];
int n;
void dfs(int start_node)
{
    road[start_node]=1;
    my_queue.push(start_node);
    while(my_queue.empty()==0)
    {
        int current_node=my_queue.front();
        my_queue.pop();
        for(int i=0; i<Graf[current_node].size(); i++)
        {
            if(road[Graf[current_node][i]]==0)
            {
                road[Graf[current_node][i]]=road[current_node]+1;
                my_queue.push(Graf[current_node][i]);
            }
        }
    }
}

void read()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        int x,y;
        in>>x>>y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }
}


int main()
{
    read();
    dfs(1);
    int max_road=0;
    int node_max;
    for(int i=1; i<=n; i++)
    {
        if(max_road<road[i])
        {
            node_max=i;
            max_road=road[i];
        }
        road[i]=0;
    }
    dfs(node_max);
    max_road=0;
    for(int i=1; i<=n; i++)
    {
        if(max_road<road[i])
        {
            max_road=road[i];
        }
    }
    out<<max_road;
}