Cod sursa(job #2207070)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 24 mai 2018 20:29:11
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
 #include<bits/stdc++.h>
 using namespace std;
 void BFS(vector<list<int> > &G, vector<int> &dist, int start)
 {
     queue<int> q;
     q.push(start);
     dist[start] = 1;
     while(!q.empty())
     {
         int nod = q.front();
         q.pop();
         for(int u : G[nod])
            if(!dist[u])
         {
             dist[u] = dist[nod] + 1;
             q.push(u);
         }
     }
 }
 int main()
 {
     ifstream in("darb.in");
     ofstream out("darb.out");
     vector<list<int> > G;
     vector<int> dist;
     int n,x,y;
     in>>n;
     G.resize(n+1);
     dist.resize(n+1,0);
     for(int i = 1; i<= n-1; i++)
     {
         in>>x>>y;
         G[x].push_back(y);
         G[y].push_back(x);
     }
     BFS(G,dist,1);
     int maxx = 0, nodStart = 1;
     for(int i = 1; i<=n; i++)
        if(dist[i] > maxx)
     {
         maxx = dist[i];
         nodStart = i;
     }
     dist.assign(n+1, 0);
     BFS(G,dist, nodStart);
     maxx = 0;
     for(int i = 1; i<=n; i++)
        if(dist[i] > maxx)
         maxx = dist[i];
        out<<maxx;
     return 0;
 }