Cod sursa(job #2446129)

Utilizator butnaru_vlad2003Butnaru Vlad butnaru_vlad2003 Data 7 august 2019 11:41:45
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
ifstream in("darb.in");
ofstream out ("darb.out");
vector <int> myvec[100001];
bool vizitat[100001];
queue <pair<int,int>> myque;
int bfs ()
{
    int sol=1,PUNCT=0;
    myque.push(make_pair(1,1));
    while (!myque.empty())
    {
        int new1=myque.front().first;
        int dist=myque.front().second;
        myque.pop();
        vizitat[new1]=1;
        for (int i=0;i<myvec[new1].size();++i)
            if (!vizitat[myvec[new1][i]])
            {
                myque.push(make_pair(myvec[new1][i],dist+1));
                vizitat[myvec[new1][i]]=1;
                PUNCT=myvec[new1][i];
                sol=max(sol,dist+1);
            }
    }
    memset(vizitat,0,sizeof(vizitat));
    myque.push(make_pair(PUNCT,1));
    while (!myque.empty())
    {
        int new1=myque.front().first;
        int dist=myque.front().second;
        myque.pop();
        vizitat[new1]=1;
        for (int i=0;i<myvec[new1].size();++i)
            if (!vizitat[myvec[new1][i]])
            {
                myque.push(make_pair(myvec[new1][i],dist+1));
                vizitat[myvec[new1][i]]=1;
                sol=max(sol,dist+1);
            }
    }
    return sol;
}
int main ()
{
    int n;
    in>>n;
    for (int i=1;i<n;++i)
    {
        int a,b;
        in>>a>>b;
        myvec[a].push_back(b);
        myvec[b].push_back(a);
    }
    out<<bfs();
}