Cod sursa(job #2461437)

Utilizator ViAlexVisan Alexandru ViAlex Data 25 septembrie 2019 18:18:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");

vector<int>adiacente[100000];
bool went[100000];
int n;

void read()
{
    in>>n;
    int a,b;

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

std::pair<int,int> get_furthest(int node)
{
    went[node]=true;
    int s=adiacente[node].size();
    int maxx=0;
    int furthest_node=node;

    for(int i=0; i<s; i++)
    {
        if(!went[adiacente[node][i]])
        {
            std::pair<int,int> data=get_furthest(adiacente[node][i]);

            if(maxx<data.first+1)
            {
                maxx=data.first+1;
                furthest_node=data.second;
            }
        }
    }

    went[node]=false;
    return std::pair<int,int>(maxx,furthest_node);
}



int main()
{
    read();
    int node=get_furthest(0).second;
    out<<get_furthest(node).first+1;

}