Cod sursa(job #2424706)

Utilizator BovisioNitica Ionut Bogdan Bovisio Data 23 mai 2019 18:26:37
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n;
int viz[100005], dist[100005];

vector<int> Graph[100005];

queue <int> MyQueue;

void Citire()
{
    int x1,x2;
    f >> n;
    for(int i=0;i<n-1;i++)
    {
        f >> x1 >> x2;
        Graph[x1].push_back(x2);
        Graph[x2].push_back(x1);
    }
}

void Init()
{
    for(int i=1;i<=n;i++)
    {
        viz[i] = 0;
        dist[i] = 0;
    }
}

void BFS(int start)
{
    int node;
    viz[start] = 1;
    dist[start] = 0;
    MyQueue.push(start);
    while(!MyQueue.empty())
    {
        node = MyQueue.front();
        MyQueue.pop();
        for(int i=0;i<Graph[node].size();i++)
        {
            int nn = Graph[node][i];
            if(viz[nn] == 0)
            {
                viz[nn] = 1;
                dist[nn] = dist[node] + 1;
                MyQueue.push(nn);
            }
        }
    }
}

void DFS(int node)
{
    viz[node] = 1;
    for(int i=0;i<Graph[node].size();i++)
    {
        int nn = Graph[node][i];
        if(viz[nn] == 0)
        {
            dist[nn] = dist[node] + 1;
            DFS(nn);
        }
    }
}

int main()
{
    int maxim = -1, nodFar;
    Citire();
    Init();
    BFS(1);
    for(int i=1;i<=n;i++)
    {
        if(dist[i] > maxim)
        {
            maxim = dist[i];
            nodFar = i;
        }
    }
    Init();
    dist[nodFar] = 0;
    DFS(nodFar);
    for(int i=1;i<=n;i++)
    {
        if(dist[i] > maxim)
        {
            maxim = dist[i];
        }
    }
    g << maxim+1;
    return 0;
}