Cod sursa(job #3146937)

Utilizator antonio_sefu_tauLaslau Antonio antonio_sefu_tau Data 23 august 2023 13:56:51
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int dim=1e5+5;
int n,viz[dim],d1[dim],d2[dim],mx;
vector<int> G[dim];
void bfs(int nod, int d[dim]){
    for(int i=1;i<=n;i++){
        viz[i]=0;
    }
    viz[nod]=1;
    queue<int> Q;
    Q.push(nod);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=0;i<G[x].size();i++){
            int u=G[x][i];
            if(!viz[u]){
                viz[u]=1;
                d[u]=d[x]+1;
                Q.push(u);
            }
        }
    }
}
int main(){
    ifstream f("darb.in");
    ofstream g("darb.out");
    f>>n;
    for(int i=1;i<n;i++){
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs(1,d1);
    int nodd;
    for(int i=1;i<=n;i++){
        if(d1[i]>mx){
            mx=d1[i];
            nodd=i;
        }
    }
    bfs(nodd,d2);
    mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,d2[i]);
    }
    g<<mx+1;
    return 0;
}