Cod sursa(job #3255495)

Utilizator aeru1Ianos Alex-Marian aeru1 Data 10 noiembrie 2024 19:07:51
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define TITLE "darb"

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

int n;

int bfs(int StartNode,vector<vector<int>> &Graph,vector<int> &Distances)
{
    Distances[StartNode]=1;
    queue<int> Q;
    int CurrentNode;
    for(Q.emplace(StartNode); !Q.empty(); Q.pop())
    {
        CurrentNode=Q.front();
        for(auto it : Graph[CurrentNode])
        if(Distances[it]==0)
        {
            Distances[it]=Distances[CurrentNode]+1;
            Q.emplace(it);
        }
    }
    return CurrentNode;
}
int main()
{
    f>>n;
    vector<vector<int>> Graph(n+1);
    for(int a,b; f>>a>>b; Graph[a].emplace_back(b), Graph[b].emplace_back(a));
    vector<int> Distances(n+1,0);
    int max1=0,max2=0;
    for(int i=1; i<=n; i++)
    {
        if(Graph[i].size()>1)
        {
            Distances[i]=1;
            for(auto it : Graph[i])
                    {
                        int help=Distances[bfs(it,Graph,Distances)];
                        if(max1<help)
                        {
                            max2=max1;
                            max1=help;
                        }
                        if(max2<help)
                            max2=help;
                    }
            break;
        }
    }
    g<<max1+max2;
    return 0;
}