Cod sursa(job #3358568)

Utilizator Octavian09Dore Octaviam Octavian09 Data 18 iunie 2026 08:17:35
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
//#include <iostream>
//#include <queue>
//#include <fstream>
//
//using namespace std;
//const int NMAX=100000;
//
//ifstream f("darb.in");
//ofstream g("darb.out");
//
//struct nod{
//    int info;
//    nod *urm;
//};
//
//nod *arb[NMAX+1];
//int n,max_dist,nod_max;
//int dist[NMAX+1];
//bool viz[NMAX+1];
//
//void add(int a,int b){
//    nod *p=new nod;
//    p->info=b;
//    p->urm=arb[a];
//    arb[a]=p;
//}
//
//void citire(){
//    int a,b;
//    f >> n;
//    for(int i=1;i<=n-1;i++){
//        f >> a >> b;
//        add(a,b);
//        add(b,a);
//    }
//}
//
//void bfs(int x){
//    queue<int> Q;
//    max_dist=1;
//    dist[x]=1;
//    viz[x]=1;
//    Q.push(x);
//    while(!Q.empty()){
//        int crt=Q.front();
//        Q.pop();
//        for(nod *p=arb[crt];p!=NULL;p=p->urm){
//            if(viz[p->info]==0){
//                dist[p->info]=dist[crt]+1;
//                if(dist[p->info]>max_dist){
//                    max_dist=dist[p->info];
//                    nod_max=p->info;
//                }
//                viz[p->info]=1;
//                Q.push(p->info);
//            }
//        }
//    }
//}
//
//void clean(){
//    for(int i=1;i<=n;i++)
//        viz[i]=0;
//}
//
//int main()
//{
//    citire();
//    bfs(1);
//    clean();
//    bfs(nod_max);
//    g << max_dist;
//    return 0;
//}

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
const int NMAX=100000;

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

int N,diam,ult;
bool viz[NMAX+1];
vector<int> lista[NMAX];

void citire(){
    int x,y;
    f >> N;
    for(int i=1;i<N;i++){
        f >> x >> y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
}

void DFS(int x,int niv){
    if(niv>diam){
        diam=niv;
        ult=x;
    }
    viz[x]=1;
    for(auto &it : lista[x])
        if(viz[it]==0)
            DFS(it,niv+1);
}

void clean(){
    for(int i=1;i<=N;i++)
        viz[i]=0;
}

int main()
{
    citire();
    DFS(1,1);
    clean();
    DFS(ult,1);
    g << diam;
    return 0;
}