Cod sursa(job #2820093)

Utilizator AndreeaGeamanuAndreea AndreeaGeamanu Data 19 decembrie 2021 21:20:23
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

#define nmax 100005


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

vector <int> la[nmax];
int dm;

int bfs(int s){
    queue <int> q;
    int v[nmax]={0},last,nc,dist[nmax]={0};

    v[s]=1;
    q.push(s);
    dist[s]=1;
    dm = 0;

    while(!q.empty()){

        nc = q.front();
        last = q.front();
        q.pop();
        v[nc] = 1;

        for(int i=0; i<la[nc].size(); i++){
            if(v[la[nc][i]]==0){
                v[la[nc][i]]=1;
                q.push(la[nc][i]);
                dist[la[nc][i]] = dist[nc] + 1;
                dm = dist[la[nc][i]];
            }
        }
    }
    return last;
}

int main()
{
    int n,i,x,y;

    f>>n;
    for(i=1; i<n; i++){
        f>>x>>y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    bfs(bfs(1));

    g<<dm;

    f.close();
    g.close();
    return 0;
}