Cod sursa(job #2815046)

Utilizator HatersMcCristian Ioan HatersMc Data 9 decembrie 2021 00:34:41
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");
int n;
vector<vector<int>> arb(100001);
vector<int> viz(100001,-1);

int bfs(int start, vector<vector<int> > mat) {
    deque<int> coada;
    vector<bool> viz(n+1 , false);
    viz[start] = true;
    int nr=0;
    coada.push_back(start);
    while (coada.empty() == false) {
        for (auto x:mat[coada[0]]) {
            if (!viz[x]) {
                nr=x;
                coada.push_back(x);
               viz[x]=true;
            }
        }
        coada.pop_front();
    }
    return nr;
}

void dfs( int n )
{
    for(int a : arb[n])
        if(viz[a]==-1){
            viz[a]=viz[n]+1;
            dfs(a);
        }

}
int main() {
 f>>n;
 int x,y;
 for(int i = 0 ; i < n ; ++i )
 {
     f>>x>>y;
     arb[x].push_back(y);
     arb[y].push_back(x);

 }
    dfs(bfs(1,arb));
    int maxim=0;
 for(int i = 1 ; i <= n ; ++i)
        if(viz[i]>maxim)
            maxim=viz[i];
    g<<maxim+2;
    return 0;
}